इस समस्या में, हमें 1 की एक धनात्मक संख्या दी गई है। हमारा कार्य क्रमबद्ध क्रम में Nवीं बाइनरी स्ट्रिंग ज्ञात करना है।
हमें a और b केवल दो प्रतीकों का उपयोग करके बनाई गई स्ट्रिंग्स की अनंत सूची में Nवीं स्ट्रिंग ढूंढनी है जो शब्दकोश क्रम में क्रमबद्ध है।
सूची है -
a, b, aa, ab, ba, bb, aaa, aab, aba, …
उदाहरण से समझते हैं:
इनपुट: N = 8 आउटपुट: aab
समाधान दृष्टिकोण
समस्या का एक सरल समाधान लूप का उपयोग करके सभी n स्ट्रिंग्स उत्पन्न करना है। और फिर Nवीं स्ट्रिंग लौटाना। यह समाधान काम करता है लेकिन N के बड़े मान के मामले में प्रभावी समाधान प्रदान नहीं कर सकता।
इसलिए, हम एक और समाधान देखेंगे जो कम समय में समाधान प्रदान कर सकता है।
समस्या को हल करने का एक अन्य दृष्टिकोण स्ट्रिंग के लिए एक सापेक्ष इंडेक्स का उपयोग करना है। इस तथ्य का उपयोग करके कि 2 प्रतीकों का उपयोग करके लंबाई N की स्ट्रिंग्स की संख्या 2^N है। सापेक्ष इंडेक्स का उपयोग बाइनरी फॉर्म स्ट्रिंग ढूंढने के लिए किया जा सकता है।
सापेक्ष इंडेक्स = N + 1 - 2( floor(log(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
