x ≤ n के उन मानों की गणना जिनके लिए (n XOR x) = (n - x) - C++

समस्या विवरण

हमें एक संख्या n दी गई है। लक्ष्य उन मानों x की गणना करना है जहाँ 0 ≤ x ≤ n और (n XOR x) = (n - x)।

उदाहरण

इनपुट: n = 10

आउटपुट: 4

व्याख्या: मान: 0, 2, 8, 10

इनपुट: n = 15

आउटपुट: 16

व्याख्या: सभी मान 0 से 15 तक वैध हैं।

दृष्टिकोण

साधारण दृष्टिकोण: 0 से n तक लूप करें और शर्त जाँचें।

कुशल दृष्टिकोण: n को बाइनरी में बदलें। प्रत्येक सेट बिट (1) के लिए, x में संबंधित बिट 0 या 1 हो सकती है (2 विकल्प)। n में p सेट बिट्स के लिए, वैध x की संख्या = 2^p।

एल्गोरिदम (कुशल)

1. n को बाइनरी स्ट्रिंग में बदलें
2. '1' बिट्स गिनें → count
3. उत्तर = 2^count
4. लौटाएँ

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

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

// साधारण दृष्टिकोण
int count_values_naive(int n) {
    int count = 0;
    for (int i = 0; i <= n; i++) {
        if (n - i == (n ^ i)) count++;
    }
    return count;
}

// कुशल दृष्टिकोण
int count_values_efficient(int n) {
    int count = 0;
    string binary = bitset<32>(n).to_string();
    for (char c : binary) if (c == '1') count++;
    return (1 << count); // 2^count
}

int main() {
    int n = 25;
    cout << "Naive: " << count_values_naive(n) << endl;
    cout << "Efficient: " << count_values_efficient(n);
    return 0;
}

आउटपुट

Naive: 8
Efficient: 8