Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में N विशिष्ट संख्याएं ढूंढना जिनका बिटवाइज OR K के बराबर हो


अवधारणा

दिए गए दो पूर्णांक N और K के संबंध में, हमारा कार्य N विशिष्ट पूर्णांक ढूंढना है जिनका बिटवाइज OR K के बराबर हो। यदि कोई संभावित उत्तर मौजूद नहीं है तो -1 प्रिंट करें।

इनपुट

N = 4, K = 6

आउटपुट

6 0 1 2

इनपुट

N = 11, K = 6

आउटपुट

-1

कोई समाधान ढूंढना संभव नहीं है।

विधि

  • हम जानते हैं कि यदि संख्याओं के अनुक्रम का बिटवाइज OR K है तो K में जो बिट इंडेक्स 0 हैं वे सभी संख्याओं में भी शून्य होने चाहिए।

  • इसके परिणामस्वरूप, हमारे पास केवल उन स्थितियों को बदलने के लिए हैं जहां K में बिट 1 है। मान लें कि गिनती Bit_K है।

  • वर्तमान में, हम Bit_K बिट्स के साथ pow(2, Bit_K) विशिष्ट संख्याएं बना सकते हैं। इसके परिणामस्वरूप, यदि हम एक संख्या को K मानते हैं, तो शेष N-1 संख्याओं को प्रत्येक संख्या में उन सभी बिट्स को 0 पर सेट करके बनाया जा सकता है जो K में 0 हैं और अन्य बिट स्थितियों के लिए Bit_K बिट्स का कोई भी क्रमपरिवर्तन संख्या K के अलावा।

  • यह देखा गया है कि यदि pow(2, Bit_K) < N तो हम कोई संभावित उत्तर निर्धारित नहीं कर सकते।

उदाहरण

// दृष्टिकोण का C++ कार्यान्वयन #include <bits/stdc++.h> using namespace std; #define ll long long int #define MAX1 32 ll pow2[MAX1]; bool visited1[MAX1]; vector<int> ans1; // MAX तक 2 की सभी घातों की पूर्व-गणना के लिए फ़ंक्शन दिखाता है void power_2(){    ll ans1 = 1;    for (int i = 0; i < MAX1; i++) {       pow2[i] = ans1;       ans1 *= 2;    } } // x में सेट बिट्स की गिनती लौटाने के लिए फ़ंक्शन दिखाता है int countSetBits(ll x1){    // सेट बिट्स की गिनती संग्रहीत करने के लिए उपयोग किया जाता है    int setBits1 = 0;    while (x1 != 0) {       x1 = x1 & (x1 - 1);       setBits1++;    }    return setBits1; } // num को उत्तर में जोड़ने के लिए फ़ंक्शन दिखाता है // सभी बिट स्थितियों को 0 पर रखकर // जो K में भी 0 हैं void add(ll num1){    int point1 = 0;    ll value1 = 0;    for (ll i = 0; i < MAX1; i++) {       // बिट i K में 0 है       if (visited1[i])          continue;       else {          if (num1 & 1) {             value1 += (1 << i);          }          num1 /= 2;       }    }    ans1.push_back(value1); } // N विशिष्ट संख्याएं ढूंढने और प्रिंट करने के लिए फ़ंक्शन दिखाता है // जिनका बिटवाइज OR K है void solve(ll n1, ll k1){    // K को स्वयं एक संख्या के रूप में चुनना    ans1.push_back(k1);    // K में सेट बिट्स की गिनती ढूंढें    int countk1 = countSetBits(k1);    // N विशिष्ट पूर्णांक प्राप्त करना संभव नहीं है    if (pow2[countk1] < n1) {       cout << -1;       return;    }    int count1 = 0;    for (ll i = 0; i < pow2[countk1] - 1; i++) {       // i को उत्तर में जोड़ें बाद       // सभी बिट्स को 0 पर रखकर       // जो K में 0 हैं       add(i);       count1++;       // अब यदि N विशिष्ट संख्याएं उत्पन्न होती हैं       if (count1 == n1)          break;    }    // अब उत्पन्न संख्याएं प्रिंट करें    for (int i = 0; i < n1; i++) {       cout << ans1[i] << " ";    } } // ड्राइवर कोड int main(){    ll n1 = 4, k1 = 6;    // सभी 2 की घातों की पूर्व-गणना    power_2();    solve(n1, k1);    return 0; }

आउटपुट

6 0 1 2

  1. - C++ में n से कम या बराबर सभी फैक्टोरियल संख्याएं खोजें

    यहां हम देखेंगे कि n से कम या बराबर सभी फैक्टोरियल संख्याओं को कैसे प्रिंट किया जाए। एक संख्या N को फैक्टोरियल संख्या कहा जाता है यदि यह किसी धनात्मक संख्या का फैक्टोरियल है। इसलिए कुछ फैक्टोरियल संख्याएं हैं: 1, 2, 6, 24, 120। फैक्टोरियल संख्याओं को प्रिंट करने के लिए, हमें सीधे फैक्टोरियल खोजने क

  1. - C++ में योग और GCD दिए जाने पर दो संख्याएं ढूंढना

    हमारे पास दो संख्याओं a और b का योग और GCD है। हमें दोनों संख्याएं a और b ढूंढनी हैं। यदि यह संभव नहीं है, तो -1 लौटाएं। मान लीजिए योग 6 है और GCD 2 है, तो संख्याएं 4 और 2 हैं।दृष्टिकोण ऐसा है, चूंकि GCD दिया गया है, तो यह ज्ञात है कि संख्याएं इसके गुणक होंगी। अब निम्न चरण हैंयदि हम पहली संख्या को G

  1. - Python में N विशिष्ट संख्याएं ढूंढना जिनका बिटवाइज OR K के बराबर हो

    मान लीजिए हमारे पास दो पूर्णांक N और K हैं; हमें N अद्वितीय मान ढूंढने हैं जिनका बिटवाइज OR, K के समान है। यदि ऐसा कोई परिणाम नहीं है, तो -1 वापस करें। तो, यदि इनपुट N = 4 और K = 6 की तरह है, तो आउटपुट [6,0,1,2] होगा। इसे हल करने के लिए, हम इन चरणों का पालन करेंगे - MAX := 32 visited := MAX आकार की