ধরুন আমাদের একটি ধনাত্মক 32-বিট পূর্ণসংখ্যা n আছে, আমাদের সবচেয়ে ছোট 32-বিট পূর্ণসংখ্যা খুঁজে বের করতে হবে যাতে এটি n-এ বিদ্যমান একই অঙ্কগুলিকে ধারণ করে এবং n-এর চেয়ে মান বড়। যদি এমন কোনো ধনাত্মক 32-বিট পূর্ণসংখ্যা না থাকে, তবে -1 ফেরত দিন।
তাই যদি সংখ্যা 213 হয়, তবে ফলাফল হবে 231।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব −
- s := n স্ট্রিং হিসেবে, sz := s-এর আকার, ok := false
- i = sz – 2 থেকে ০ পর্যন্ত
- যদি s[i] < s[i + 1], তবে ok := true এবং লুপ ভাঙুন
- যদি ok false হয়, তবে – ১ ফেরত দিন
- smallest := i, curr := i + 1
- j = i + 1 থেকে sz – ১ পর্যন্ত
- যদি s[j] > s[smallest] এবং s[j] <= s[curr], তবে curr := j
- s[smallest] এবং s[curr] বদলান
- aux := s-এর সাবস্ট্রিং ইনডেক্স ০ থেকে smallest পর্যন্ত
- aux উল্টান
- ret := s-এর সাবস্ট্রিং ইনডেক্স ০ থেকে smallest + ১ + aux
- যদি ret 32-বিট ধনাত্মক পূর্ণসংখ্যার পরিসরের চেয়ে বড় হয় তবে -1 ফেরত দিন, অন্যথায় ret
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন −
উদাহরণ
#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
