ধরুন আমাদের একটি ধনাত্মক 32-বিট পূর্ণসংখ্যা n আছে, আমাদেরকে সবচেয়ে ছোট 32-বিট পূর্ণসংখ্যাটি খুঁজে বের করতে হবে যেটির পূর্ণসংখ্যা n-এ বিদ্যমান একই সংখ্যা রয়েছে এবং n-এর থেকে মান বেশি। যদি আমাদের কাছে এমন কোনো ইতিবাচক 32-বিট পূর্ণসংখ্যা না থাকে, তাহলে -1 ফেরত দিন।
সুতরাং সংখ্যাটি যদি 213 হয়, তাহলে ফলাফল 231 হবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- s :=n স্ট্রিং হিসাবে, sz :=s এর আকার, ঠিক আছে :=মিথ্যা
- sz - 2 থেকে 0
- রেঞ্জে i জন্য
- যদি s[i]
- যদি s[i]
- যদি মিথ্যা হয়, তাহলে ফিরুন – 1
- সবচেয়ে ছোট :=i, curr :=i + 1
- j-এর জন্য i + 1 থেকে sz – 1
- পরিসরে
- id s[j]> s[smallest] এবং s[j] <=s[curr], তারপর curr :=j
- s[smallest] এর সাথে s[curr] বিনিময় করুন
- aux :=সূচক 0 থেকে ক্ষুদ্রতম পর্যন্ত s এর সাবস্ট্রিং
- রিভার্স অক্স
- ret :=সূচক 0 থেকে ক্ষুদ্রতম + aux পর্যন্ত s এর সাবস্ট্রিং
- রিটার্ন -1 যদি ret হয়> 32-বিট +ve পূর্ণসংখ্যা পরিসীমা, অন্যথায় রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int nextGreaterElement(int n) {
string s = to_string(n);
int sz = s.size();
int i;
bool ok = false;
for(i = sz - 2; i >= 0; i--){
if(s[i] < s[i + 1]) {
ok = true;
break;
}
}
if(!ok) return -1;
int smallest = i;
int curr = i + 1;
for(int j = i + 1; j < sz; j++){
if(s[j] > s[smallest] && s[j] <= s[curr]){
curr = j;
}
}
swap(s[smallest], s[curr]);
string aux = s.substr(smallest + 1);
reverse(aux.begin(), aux.end());
string ret = s.substr(0, smallest + 1) + aux;
return stol(ret) > INT_MAX ? -1 : stol(ret);
}
};
main(){
Solution ob;
cout << (ob.nextGreaterElement(213));
} ইনপুট
213
আউটপুট
231
