Find N distinct numbers whose bitwise Or is equal to K | Pyhton 3 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
MAX = 32 NEW_LINE pow2 = [ 0 for i in range ( MAX ) ] NEW_LINE visited = [ False for i in range ( MAX ) ] NEW_LINE ans = [ ] NEW_LINE def power_2 ( ) : NEW_LINE INDENT an = 1 NEW_LINE for i in range ( MAX ) : NEW_LINE INDENT pow2 [ i ] = an NEW_LINE an *= 2 NEW_LINE DEDENT DEDENT def countSetBits ( x ) : NEW_LINE INDENT setBits = 0 NEW_LINE while ( x != 0 ) : NEW_LINE INDENT x = x & ( x - 1 ) NEW_LINE setBits += 1 NEW_LINE DEDENT return setBits NEW_LINE DEDENT def add ( num ) : NEW_LINE INDENT point = 0 NEW_LINE value = 0 NEW_LINE for i in range ( MAX ) : NEW_LINE INDENT if ( visited [ i ] ) : NEW_LINE INDENT continue NEW_LINE DEDENT else : NEW_LINE INDENT if ( num & 1 ) : NEW_LINE INDENT value += ( 1 << i ) NEW_LINE DEDENT num = num // 2 NEW_LINE DEDENT DEDENT ans . append ( value ) NEW_LINE DEDENT def solve ( n , k ) : NEW_LINE INDENT ans . append ( k ) NEW_LINE countk = countSetBits ( k ) NEW_LINE if ( pow2 [ countk ] < n ) : NEW_LINE INDENT print ( - 1 ) NEW_LINE return NEW_LINE DEDENT count = 0 NEW_LINE for i in range ( pow2 [ countk ] - 1 ) : NEW_LINE INDENT add ( i ) NEW_LINE count += 1 NEW_LINE if ( count == n ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT print ( ans [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 3 NEW_LINE k = 5 NEW_LINE power_2 ( ) NEW_LINE solve ( n , k ) NEW_LINE DEDENT