সি++-এ সংখ্যার পরবর্তী পারমুটেশন খুঁজে বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি সংখ্যা n দেওয়া আছে। এর ডিজিটগুলোর পরবর্তী বড় পারমুটেশন খুঁজে বের করতে হবে। যদি ইতিমধ্যে সবচেয়ে বড় পারমুটেশন হয়, তবে সবচেয়ে ছোট পারমুটেশনে রোটেট করুন।

উদাহরণ: n = 319 → আউটপুট 391।

সমাধানের পদ্ধতি

1. সংখ্যকে ডিজিট অ্যারেতে রূপান্তর করুন।
2. ডান পাশ থেকে বামে যেতে প্রথম olyan ইনডেক্স i খুঁজুন যাতে digits[i] < digits[i+1]।
3. যদি না পাওয়া যায় → অ্যারেটি সর্ট করুন (সবচেয়ে ছোট পারমুটেশন)।
4. অন্যথায়, i+1 থেকে শেষ পর্যন্ত থেকে digits[i]-এর চেয়ে বড় সবচেয়ে ছোট ডিজিট খুঁজে সওয়াপ করুন।
5. i+1 থেকে শেষ পর্যন্ত সর্ট করুন।
6. অ্যারেকে সংখ্যায় রূপান্তর করুন।

উদাহরণ কোড

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> makeArray(int x) {
        vector<int> ret;
        while (x) { ret.push_back(x % 10); x /= 10; }
        reverse(ret.begin(), ret.end());
        return ret;
    }
    int combine(vector<int>& v) {
        int ret = 0;
        for (int i : v) { ret *= 10; ret += i; }
        return ret;
    }
    int getIndex(vector<int>& v) {
        int ret = -1;
        for (int i = v.size()-1; i >= 1; i--)
            if (v[i] > v[i-1]) { ret = i; break; }
        if (ret != -1) {
            int x = v[ret-1], idx = ret;
            for (int j = ret+1; j < v.size(); j++)
                if (v[j] < v[idx] && v[j] > x) idx = j;
            swap(v[ret-1], v[idx]);
        }
        return ret;
    }
    int solve(int num) {
        vector<int> v = makeArray(num);
        int idx = getIndex(v);
        if (idx == -1) sort(v.begin(), v.end());
        else sort(v.begin() + idx, v.end());
        return combine(v);
    }
};

int main() {
    int n = 319;
    cout << solve(n);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: 319

আউটপুট: 391