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