इस समस्या में, हमें एक धनात्मक पूर्णांक दिया जाता है। हमारा काम अधिकतम एक स्वैप ऑपरेशन का उपयोग करके छोटी संख्या बनाने के लिए एक प्रोग्राम बनाना है।
हम मौजूदा संख्या के अंकों का उपयोग करके एक नई संख्या बनाएंगे। गठित सबसे छोटी संख्या में मौजूदा संख्या से केवल एक अंक की अदला-बदली हो सकती है।
समस्या को समझने के लिए एक उदाहरण लेते हैं
Input: n = 63519 Output: 36519
समाधान दृष्टिकोण
समस्या को हल करने की एक विधि दी गई संख्या के अंकों की जोड़ी को स्वैप करके बनाई गई सभी संख्याओं को ढूंढकर है। इन सभी अदला-बदली अंकों में से, सबसे छोटी संख्या को वापस कर दिया जाता है। इसके लिए हम नंबर को स्ट्रिंग और स्वैप पोजीशन में बदल देंगे।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#include <iostream>
using namespace std;
int findSmallestNumSwapDig(int N){
string strNum = to_string(N);
string temp = 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(temp))
temp = strNum;
swap(strNum[i], strNum[j]);
}
}
return stoi(temp);
}
int main(){
int num = 792156;
cout<<"The number is "<<num<<endl;
cout<<"The smallest number created by swapping one digit is "<<findSmallestNumSwapDig(num) << endl;
return 0;
} आउटपुट
The number is 792156 The smallest number created by swapping one digit is192756
एक और तरीका
समस्या को हल करने का एक और तरीका एक अतिरिक्त सहायक सरणी 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();
int auxArr[n], right;
auxArr[n - 1] = -1;
right = n - 1;
for (int i = n - 2; i >= 1; i--) {
if (num[i] >= num[right])
auxArr[i] = right;
else {
if (num[i] == num[i + 1])
auxArr[i] = right;
else {
auxArr[i] = -1;
right = i;
}
}
}
int small = -1;
for (int i = 1; i < n; i++)
if (num[i] != '0') {
if (small == -1) {
if (num[i] < num[0])
small = i;
}
else if (num[i] <= num[small])
small = i;
}
if (small != -1)
swap(num[0], num[small]);
else {
for (int i = 1; i < n; i++) {
if (auxArr[i] != -1 && num[i] != num[auxArr[i]]) {
swap(num[i], num[auxArr[i]]);
break;
}
}
}
return stoi(num);
}
int main(){
int num = 792156;
cout<<"The number is "<<num<<endl;
cout<<"The smallest number created by swapping one digit is" <<findSmallestNumSwapDig(num)<< endl;
return 0;
} आउटपुट
The number is 792156 The smallest number created by swapping one digit is192756