C++ में N से छोटी बाइनरी अंक संख्याओं की गिनती

समस्या विवरण

एक पूर्णांक N इनपुट के रूप में दिया गया है। लक्ष्य उन पूर्णांकों की संख्या ज्ञात करना है जो N से कम हैं और बाइनरी रूप में दर्शाए गए हैं। उदाहरण के लिए, यदि इनपुट N=12 है, तो 12 से छोटी संख्याएं 1, 10, 11 हैं जो बाइनरी हैं और जिनमें केवल 0 और 1 अंक होते हैं। उत्तर 3 होगा।

उदाहरण

इनपुट

N=100

आउटपुट

N से छोटी बाइनरी अंक संख्याओं की गिनती: 4

व्याख्या

100 से छोटी बाइनरी संख्याएं: 1, 10, 11, 100

इनपुट

N=120

आउटपुट

N से छोटी बाइनरी अंक संख्याओं की गिनती: 7

व्याख्या

100 से छोटी बाइनरी संख्याएं: 1, 10, 11, 100, 101, 110, 111

दृष्टिकोण

इस दृष्टिकोण में हम एक पूर्णांक वेक्टर vec का उपयोग करते हैं। इसमें हम पहले 1 डालते हैं। अगली बाइनरी संख्या उत्पन्न करने के लिए हम vec से अंतिम संख्या (temp) निकालते हैं (प्रारंभ में 1)। फिर अगली संख्या उत्पन्न करते हैं: temp*10 और temp*10+1 क्योंकि बाइनरी संख्याएं हमेशा (1, 10, 11, 100, 110, 111...) होती हैं। vec से संख्याएं निकालें और यदि यह N से कम है तो गिनती बढ़ाएं।

एल्गोरिदम चरण

एक पूर्णांक N इनपुट के रूप में लें।
फंक्शन Smaller_N(int N) N लेता है और N से छोटी बाइनरी अंक संख्याओं की गिनती लौटाता है।
प्रारंभिक गिनती 0 लें।
केवल 0 और 1 अंक वाली पूर्णांकों को संग्रहीत करने के लिए पूर्णांक वेक्टर vec लें।
vec.push_back(1) का उपयोग करके 1 को वेक्टर में जोड़ें।
while लूप का उपयोग करके vec[] को पार करें और अंतिम डाली गई संख्या को temp = vec.back() के रूप में लें। और इसे vec से हटा दें।
यदि temp <= N, तो गिनती बढ़ाएं और अगली बाइनरी पूर्णांक temp*10 और temp*10+1 के रूप में उत्पन्न करें और vec में जोड़ें।
लूप के अंत में गिनती को परिणाम के रूप में लौटाएं।

C++ कोड उदाहरण

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

int Smaller_N(int N) {
    int count = 0;
    vector<int> vec;
    vec.push_back(1);
    
    while (!vec.empty()) {
        int temp = vec.back();
        vec.pop_back();
        
        if (temp <= N) {
            count++;
            int temp_2 = temp * 10;
            vec.push_back(temp_2);
            vec.push_back(temp_2 + 1);
        }
    }
    return count;
}

int main() {
    int N = 1000;
    cout << "N से छोटी बाइनरी अंक संख्याओं की गिनती: " << Smaller_N(N);
    return 0;
}

आउटपुट

N से छोटी बाइनरी अंक संख्याओं की गिनती: 8