C++ में अधिकतम K स्वैप करके अधिकतम संभव संख्या ज्ञात करें

इस समस्या में, हमें दो पूर्णांक मान n और k दिए गए हैं। हमारा कार्य अधिकतम K स्वैप करके अधिकतम संभव संख्या ज्ञात करना है।

समस्या का विवरण: यहां, हमें उस संख्या की गणना करने की आवश्यकता है जो अधिकतम है और संख्या के अधिकतम k अंकों की अदला-बदली के बाद बनाई गई है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट: n =538 k =1

आउटपुट: 835

स्पष्टीकरण:

हम 8 और 5 की अदला-बदली करेंगे।

समाधान दृष्टिकोण

समस्या को हल करने के लिए, हमें k बार संख्या के अंकों को स्वैप करना होगा और जांचना होगा कि संख्या अधिकतम है या नहीं।

हमें संख्या का अधिकतम अंक खोजने की जरूरत है और फिर पहले सूचकांक में तत्व को स्वैप करें। और इसी तरह संख्याओं के पहले k सूचकांक के लिए।

हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम

उदाहरण

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

void calcMaxNumAfterSwap(string number, int k, string& maxString, int n){
   
   if (k == 0)
      return;
   for (int i = 0; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) {
         if (number[i] < number[j]) {
            swap(number[i], number[j]);
            if (number.compare(maxString) > 0)
               maxString = number;
            calcMaxNumAfterSwap(number, k - 1, maxString, n);
            swap(number[i], number[j]);
         }
      }
   }
}

int main(){
   
   string str = "15263";
   int k = 3;
   int size = str.length();
   string maxString = str;
   calcMaxNumAfterSwap(str, k, maxString, size);
   cout<<"The maximum number created after "<<k<<" swaps is "<<maxString;

   return 0;
}

आउटपुट

The maximum number created after 3 swaps is 65321