এই সমস্যাতে, আমাদের একটি পজিটিভ ইন্টিজার দেওয়া আছে। আমাদের কাজ হল সর্বোচ্চ একবার সওয়াপ (Swap) অপারেশন ব্যবহার করে সবচেয়ে ছোট সংখ্যা তৈরি করার প্রোগ্রাম তৈরি করা।
আমরা দেয়া সংখ্যার ডিজিট ব্যবহার করে একটি নতুন সংখ্যা তৈরি করব। সবচেয়ে ছোট সংখ্যা তৈরি করতে হলে শুধু এক জোড়া ডিজিট সওয়াপ করা যাবে।
উদাহরণ দেখি:
ইনপুট: n = 63519 আউটপুট: 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[] ব্যবহার করা। এই অ্যারেটি করেন্ট ইনডেক্স i-র ডানে (বড় ইনডেক্সে) সবচেয়ে ছোট ডিজিটের ইনডেক্স স্টোর করতে ব্যবহৃত হয়। অর্থাৎ aux[i] হল সংখ্যার ডিজিটের ডান পাশে সবচেয়ে ছোট ডিজিটের ইনডেক্স। aux[i] = -1 ইনিশিয়ালাইজ করুন, যদি এমন কোনো ডিজিট না থাকে। এখন, অ্যারেটি ০ থেকে n-1 পর্যন্ত ট্রাভার্স করে aux[]-এ থাকা সংখ্যা করেন্ট ভ্যালুর চেয়ে ছোট কিনা চেক করুন। ইনডেক্স ০-এর ভ্যালুর জন্য নন-জিরো এলিমেন্ট চেক করুন, যদি ০ থাকে তবে বাদ দিন। যদি কোনো এলিমেন্ট পাওয়া যায়, তবে 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
