C++ में बाइनरी स्ट्रिंग विद सबस्ट्रिंग्स रिप्रेजेंटिंग 1 टू N (Binary String With Substrings Representing 1 To N)

मान लीजिए हमारे पास एक बाइनरी स्ट्रिंग S और एक धनात्मक पूर्णांक N है, हमें true कहना है यदि और केवल यदि 1 से N तक प्रत्येक पूर्णांक X के लिए, X का बाइनरी प्रतिनिधित्व दिए गए S का उपस्ट्रिंग है।

उदाहरण के लिए, यदि S = "0110" और N = 3, तो परिणाम true होगा, क्योंकि 1, 10 और 11 सभी 0110 में मौजूद हैं।

समाधान दृष्टिकोण

1. convert() विधि परिभाषित करें जो n को बाइनरी स्ट्रिंग में बदलती है

2. मुख्य विधि से, i = N से N/2 तक घटाते हुए लूप चलाएं

3. प्रत्येक i को बाइनरी में बदलकर S में खोजें

4. यदि कोई नहीं मिला तो false लौटाएं, अन्यथा true

C++ कार्यान्वयन

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    string convert(int n){ 
        string ret = ""; 
        while(n){ 
            ret += (n % 2) + '0'; 
            n /= 2; 
        } 
        reverse(ret.begin(), ret.end()); 
        return ret; 
    } 
    
    bool queryString(string S, int N) { 
        for(int i = N; i >= N/2; i-- ){ 
            string temp = convert(i); 
            if(S.find(temp) == string::npos) return false; 
        } 
        return true; 
    } 
}; 

int main(){ 
    Solution ob; 
    cout << (ob.queryString("0110", 3)); 
    return 0; 
}

इनपुट

"0110" 3

आउटपुट

1