N भिन्न संख्याएँ ज्ञात कीजिए जिनका बिटवाइज़ या C++ में K के बराबर है

अवधारणा

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

इनपुट

N = 4, K = 6

आउटपुट

6 0 1 2

इनपुट

N = 11, K = 6

आउटपुट

-1

कोई समाधान खोजना संभव नहीं है।

विधि

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

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

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

• यह देखा गया है कि यदि pow(2, Bit_K)

उदाहरण

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define MAX1 32
ll pow2[MAX1];
bool visited1[MAX1];
vector<int> ans1;
// Shows function to pre-calculate
// all the powers of 2 upto MAX
void power_2(){
   ll ans1 = 1;
   for (int i = 0; i < MAX1; i++) {
      pow2[i] = ans1;
      ans1 *= 2;
   }
}
// Shows function to return the
// count of set bits in x
int countSetBits(ll x1){
   // Used to store the count
   // of set bits
   int setBits1 = 0;
   while (x1 != 0) {
      x1 = x1 & (x1 - 1);
      setBits1++;
   }
   return setBits1;
}
// Shows function to add num to the answer
// by placing all bit positions as 0
// which are also 0 in K
void add(ll num1){
   int point1 = 0;
   ll value1 = 0;
   for (ll i = 0; i < MAX1; i++) {
      // Bit i is 0 in K
      if (visited1[i])
         continue;
      else {
         if (num1 & 1) {
            value1 += (1 << i);
         }
         num1 /= 2;
      }
   }
   ans1.push_back(value1);
}
// Shows function to find and print N distinct
// numbers whose bitwise OR is K
void solve(ll n1, ll k1){
   // Choosing K itself as one number
   ans1.push_back(k1);
   // Find the count of set bits in K
   int countk1 = countSetBits(k1);
   // It is not possible to get N
   // distinct integers
   if (pow2[countk1] < n1) {
      cout << -1;
      return;
   }
   int count1 = 0;
   for (ll i = 0; i < pow2[countk1] - 1; i++) {
      // Add i to the answer after
      // placing all the bits as 0
      // which are 0 in K
      add(i);
      count1++;
      // Now if N distinct numbers are generated
      if (count1 == n1)
         break;
   }
   // Now print the generated numbers
   for (int i = 0; i < n1; i++) {
      cout << ans1[i] << " ";
   }
}
// Driver code
int main(){
   ll n1 = 4, k1 = 6;
   // Pre-calculate all
   // the powers of 2
   power_2();
   solve(n1, k1);
   return 0;
}

आउटपुट

6 0 1 2