C++ में अधिकतम एक स्वैप ऑपरेशन का उपयोग करके सबसे छोटी संख्या बनाना

समस्या विवरण

इस समस्या में, हमें एक धनात्मक पूर्णांक दिया गया है। हमारा कार्य अधिकतम एक स्वैप ऑपरेशन का उपयोग करके सबसे छोटी संख्या बनाने के लिए एक प्रोग्राम बनाना है।

हम मौजूदा संख्या के अंकों का उपयोग करके एक नई संख्या बनाएंगे। बनाई गई सबसे छोटी संख्या में मौजूदा संख्या से केवल एक अंक की अदला-बदली हो सकती है।

उदाहरण

इनपुट: n = 63519
आउटपुट: 36519

व्याख्या: 6 और 3 को स्वैप करने से 36519 प्राप्त होता है जो संभव सबसे छोटी है।

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

विधि 1: ब्रूट फोर्स (O(D²)) जहां D = अंकों की संख्या

समस्या को हल करने की एक विधि दिए गए संख्या के अंकों के जोड़े को स्वैप करके बनाई गई सभी संख्याओं को खोजना है। इन सभी स्वैप की गई संख्याओं में से, सबसे छोटी को वापस करें। इसके लिए, हम संख्या को स्ट्रिंग में बदलेंगे और स्थितियों को स्वैप करेंगे।

#include <iostream> 
#include <string> 
#include <algorithm> 
using namespace std; 

int findSmallestNumSwapDig(int N) {
    string strNum = to_string(N);
    string best = strNum;
    
    for (int i = 0; i < strNum.size(); i++) {
        for (int j = i + 1; j < strNum.size(); j++) {
            swap(strNum[i], strNum[j]);
            if (stoi(strNum) < stoi(best))
                best = strNum;
            swap(strNum[i], strNum[j]); // वापस स्वैप करें
        }
    }
    return stoi(best);
}

int main() {
    int num = 792156;
    cout << "संख्या है " << num << endl;
    cout << "एक अंक स्वैप करके बनी सबसे छोटी संख्या है " 
         << findSmallestNumSwapDig(num) << endl;
    return 0;
}

विधि 2: अनुकूलित O(D) दृष्टिकोण

समस्या को हल करने का एक और दृष्टिकोण एक अतिरिक्त सहायक सरणी aux[] का उपयोग करना है। यह सरणी वर्तमान इंडेक्स के दाईं ओर (बड़े इंडेक्स) सबसे छोटे अंक का इंडेक्स संग्रहीत करने के लिए उपयोग की जाती है यानी aux[i] वर्तमान इंडेक्स के दाईं ओर सबसे छोटे अंक का इंडेक्स है। aux[i] = -1 प्रारंभ करें, यदि ऐसा कोई अंक मौजूद नहीं है। अब, संख्या को इंडेक्स 0 से n-1 तक पार करें और aux[] सरणी में उस संख्या को खोजें जो वर्तमान मान से छोटी है। इंडेक्स 0 के मान के लिए, गैर-शून्य तत्व की जांच करें, यदि 0 आता है तो मान को अस्वीकार करें। यदि कोई तत्व मिलता है, तो arr[i] और arr[aux[i]] को स्वैप करें और बनी संख्या वापस करें।

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

int findSmallestNumSwapDig(int N) {
    string num = to_string(N);
    int n = num.size();
    vector<int> aux(n, -1);
    int right = n - 1;
    
    // दाएं से बाएं: प्रत्येक स्थिति के लिए दाईं ओर सबसे छोटा अंक खोजें
    aux[n - 1] = -1;
    for (int i = n - 2; i >= 1; i--) {
        if (num[i] >= num[right])
            aux[i] = right;
        else {
            if (num[i] == num[i + 1])
                aux[i] = right;
            else {
                aux[i] = -1;
                right = i;
            }
        }
    }
    
    // पहली स्थिति के लिए विशेष हैंडलिंग (लीडिंग जीरो नहीं)
    int smallestNonZero = -1;
    for (int i = 1; i < n; i++) {
        if (num[i] != '0') {
            if (smallestNonZero == -1 || num[i] <= num[smallestNonZero])
                smallestNonZero = i;
        }
    }
    
    if (smallestNonZero != -1 && num[smallestNonZero] < num[0]) {
        swap(num[0], num[smallestNonZero]);
    } else {
        // अन्य स्थितियों के लिए aux का उपयोग करें
        for (int i = 1; i < n; i++) {
            if (aux[i] != -1 && num[i] != num[aux[i]]) {
                swap(num[i], num[aux[i]]);
                break;
            }
        }
    }
    return stoi(num);
}

int main() {
    int num = 792156;
    cout << "संख्या है " << num << endl;
    cout << "एक अंक स्वैप करके बनी सबसे छोटी संख्या है " 
         << findSmallestNumSwapDig(num) << endl;
    return 0;
}

आउटपुट

संख्या है 792156
एक अंक स्वैप करके बनी सबसे छोटी संख्या है 192756

जटिलता विश्लेषण

मुख्य अंतर्दृष्टि

• बाएं से दाएं स्कैन करें, पहले स्थान को खोजें जहां दाईं ओर एक छोटा अंक मौजूद है
• पहले अंक के लिए, सुनिश्चित करें कि स्वैप किया गया अंक 0 नहीं है
• दाईं ओर सबसे छोटे अंक के सबसे दाएं घटना के साथ स्वैप करें