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

समस्या विवरण

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

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

उदाहरण

इनपुट: n = 63512
आउटपुट: 65312

व्याख्या: 3 और 5 को स्वैप करने से 65312 प्राप्त होता है।

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

विधि 1: ब्रूट फोर्स (O(D²))

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

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

int findLargestNumSwapDig(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 << "एक अंक स्वैप करके बनी सबसे बड़ी संख्या है " 
         << findLargestNumSwapDig(num) << endl;
    return 0;
}

विधि 2: अनुकूलित O(D) - दाएं से बाएं स्कैन

समस्या को हल करने का एक और दृष्टिकोण वह स्वैप खोजना है जो सबसे बड़ी संभव संख्या में योगदान देता है। इसके लिए, हम संख्या को दाएं से बाएं स्कैन करेंगे। और फिर उस पहले जोड़े को स्वैप करेंगे जहां अगला अंक पिछले अंक से बड़ा है। यह स्वैप सबसे बड़ी संख्या में परिणाम देगा।

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

int findLargestNumSwapDig(int N) {
    string strNum = to_string(N);
    int n = strNum.size();
    
    int maxDigit = -1;
    int maxIdx = -1;
    int leftSwap = -1, rightSwap = -1;
    
    // दाएं से बाएं स्कैन करें
    for (int i = n - 1; i >= 0; i--) {
        int digit = strNum[i] - '0';
        if (digit > maxDigit) {
            maxDigit = digit;
            maxIdx = i;
        } else if (digit < maxDigit) {
            // दाईं ओर बड़ा अंक मिला
            leftSwap = i;
            rightSwap = maxIdx;
        }
    }
    
    if (leftSwap == -1)
        return N; // पहले से ही सबसे बड़ा संभव
    
    swap(strNum[leftSwap], strNum[rightSwap]);
    return stoi(strNum);
}

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

आउटपुट

संख्या है 792156
एक अंक स्वैप करके बनी सबसे बड़ी संख्या है 972156

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

एल्गोरिदम अंतर्ज्ञान

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