Find N distinct numbers whose bitwise Or is equal to K in C++

Concept

With respect of given two integers N and K, our task is to determine N distinct integers whose bitwise OR is equal to K. It has been seen that if there does not exist any possible answer then print -1.

Input

N = 4, K = 6

Output

6 0 1 2

Input

N = 11, K = 6

Output

-1

It is not possible to find any solution.

Method

• We have knowledge that if bit-wise OR of a sequence of numbers is K then all the bit indexes which are 0 in K must also be zero in all the numbers.

• As a result of this, we only have those positions to change where bit is 1 in K. Let that count is Bit_K.

• At present, we can create pow(2, Bit_K) distinct numbers with Bit_K bits. As a result of this, if, we treat one number to be K itself, then remaining N – 1 numbers can be built by setting 0 all the bits in each and every number which are0 in K and for other bit positions any permutation of Bit_K bits other than number K.

• It has been seen that if pow(2, Bit_K) < N then we cannot determine any possible answer.

Example

 Live Demo

// 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; }

Output

6 0 1 2