এই সমস্যায়, আমাদেরকে 1 এর একটি ধনাত্মক সংখ্যা দেওয়া হয়েছে। আমাদের কাজ হল সাজানো ক্রমে Nth বাইনারি স্ট্রিং খুঁজে বের করা।
আভিধানিক ক্রমানুসারে মাত্র দুটি প্রতীক a এবং b ব্যবহার করে তৈরি করা স্ট্রিংগুলির একটি অসীম তালিকায় আমাদের Nth স্ট্রিংটি খুঁজে বের করতে হবে৷
তালিকাটি হল -
a, b, aa, ab, ba, bb, aaa, aab, aba, …
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : N = 8 Output : aab
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল লুপ ব্যবহার করে সমস্ত এন স্ট্রিং তৈরি করা। এবং তারপর Nth স্ট্রিং ফিরে. এই সমাধানটি কাজ করে কিন্তু N.
এর বড় মানের ক্ষেত্রে একটি কার্যকর সমাধান দিতে পারে নাসুতরাং, আমরা আরেকটি সমাধান দেখব যা কম সময়ে সমাধান দিতে পারে।
সমস্যা সমাধানের আরেকটি পদ্ধতি হল স্ট্রিংয়ের জন্য একটি আপেক্ষিক সূচক ব্যবহার করে। 2 চিহ্ন ব্যবহার করে N দৈর্ঘ্যের স্ট্রিংগুলির সংখ্যা 2N তৈরি করা যায় তা ব্যবহার করে। আপেক্ষিক সূচকটি বাইনারী ফর্ম খুঁজে পেতে ব্যবহার করা যেতে পারে স্ট্রিং।
আপেক্ষিক সূচক =N + 1 - 2( ফ্লোর(লগ(N+1)) )
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
string findBinString(ll n){
ll len = (int)log2(n + 1);
int ri = n + 1 - pow(2, len);
ll i = 0;
string binString = "";
for (i = 0; i < len; i++) {
binString += 'a';
}
i = 0;
while (ri > 0) {
if (ri % 2 == 1)
binString[i] = 'b';
ri /= 2;
i++;
}
reverse(binString.begin(), binString.end());
return binString;
}
int main(){
ll n = 245;
cout<<"The "<<n<<"-th binary string in sorted order is "<<findBinString(n);
return 0;
} আউটপুট
The 245-th binary string in sorted order is bbbabba
