अवधारणा
दिए गए दो पूर्णांक 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