Find N distinct numbers whose bitwise Or is equal to K | C ++ implementation of the approach ; Function to pre - calculate all the powers of 2 upto MAX ; Function to return the count of set bits in x ; To store the count of set bits ; Function to add num to the answer by setting all bit positions as 0 which are also 0 in K ; Bit i is 0 in K ; Function to find and print N distinct numbers whose bitwise OR is K ; Choosing K itself as one number ; Find the count of set bits in K ; Impossible to get N distinct integers ; Add i to the answer after setting all the bits as 0 which are 0 in K ; If N distinct numbers are generated ; Print the generated numbers ; Driver code ; Pre - calculate all the powers of 2
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long int NEW_LINE #define MAX  32 NEW_LINE ll pow2 [ MAX ] ; bool visited [ MAX ] ; vector < int > ans ; void power_2 ( ) { ll ans = 1 ; for ( int i = 0 ; i < MAX ; i ++ ) { pow2 [ i ] = ans ; ans *= 2 ; } } int countSetBits ( ll x ) { int setBits = 0 ; while ( x != 0 ) { x = x & ( x - 1 ) ; setBits ++ ; } return setBits ; } void add ( ll num ) { int point = 0 ; ll value = 0 ; for ( ll i = 0 ; i < MAX ; i ++ ) { if ( visited [ i ] ) continue ; else { if ( num & 1 ) { value += ( 1 << i ) ; } num /= 2 ; } } ans . push_back ( value ) ; } void solve ( ll n , ll k ) { ans . push_back ( k ) ; int countk = countSetBits ( k ) ; if ( pow2 [ countk ] < n ) { cout << -1 ; return ; } int count = 0 ; for ( ll i = 0 ; i < pow2 [ countk ] - 1 ; i ++ ) { add ( i ) ; count ++ ; if ( count == n ) break ; } for ( int i = 0 ; i < n ; i ++ ) { cout << ans [ i ] << " ▁ " ; } } int main ( ) { ll n = 3 , k = 5 ; power_2 ( ) ; solve ( n , k ) ; return 0 ; }