C++ में किसी संख्या का अगला पूर्णांक क्रमपरिवर्तन प्राप्त करने का प्रोग्राम

समस्या विवरण

मान लीजिए हमारे पास एक संख्या n है, हमें इसके अंकों का अगला बड़ा क्रमपरिवर्तन ढूंढना है। जब n पहले से ही अपने सबसे बड़े क्रमपरिवर्तन में है, तो इसे सबसे छोटे क्रमपरिवर्तन पर घुमाएं।

उदाहरण के लिए, यदि इनपुट है n = 319, तो आउटपुट 391 होगा।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

1. एक फंक्शन makeArray() परिभाषित करें जो x लेता है
2. एक ऐरे ret परिभाषित करें
3. जब तक x शून्येतर है:
   • x mod 10 को ret के अंत में डालें
   • x := x / 10
4. ret ऐरे को रिवर्स करें
5. ret वापस करें
6. एक फंक्शन combine() परिभाषित करें जो एक ऐरे v लेता है
7. ret := 0
8. v में प्रत्येक तत्व i के लिए: ret := ret * 10, ret := ret + i
9. ret वापस करें
10. एक फंक्शन getIndex() परिभाषित करें जो एक ऐरे v लेता है
11. ret := -1
12. i := v के आकार से 1 तक (घटते क्रम में):
    • यदि v[i] > v[i-1], तो ret := i, लूप से बाहर निकलें
13. यदि ret != -1:
    • x := v[ret-1]
    • idx := ret
    • j := ret+1 से v के आकार तक:
      • यदि v[j] < v[idx] और v[j] > x, तो idx := j
    • v[ret-1] और v[idx] को स्वैप करें
14. ret वापस करें
15. मुख्य विधि से:
    • v := makeArray(num)
    • idx := getIndex(v)
    • यदि idx == -1, तो v को सॉर्ट करें
    • अन्यथा v को idx से अंत तक सॉर्ट करें
    • combine(v) वापस करें

उदाहरण

#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];
            int 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 solve(int n) {
    return (new Solution())->solve(n);
}

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

इनपुट

319

आउटपुट

391