Print N | Function to get the binary representation of the number N ; loop for each bit ; generate numbers in the range of ( 2 ^ N ) - 1 to 2 ^ ( N - 1 ) inclusive ; longest prefix check ; if counts of 1 is greater than counts of zero ; do sub - prefixes check ; Driver code ; Function call
def getBinaryRep ( N , num_of_bits ) : NEW_LINE INDENT r = " " ; NEW_LINE num_of_bits -= 1 NEW_LINE while ( num_of_bits >= 0 ) : NEW_LINE INDENT if ( N & ( 1 << num_of_bits ) ) : NEW_LINE INDENT r += ( "1" ) ; NEW_LINE DEDENT else : NEW_LINE INDENT r += ( "0" ) ; NEW_LINE DEDENT num_of_bits -= 1 NEW_LINE DEDENT return r ; NEW_LINE DEDENT def NBitBinary ( N ) : NEW_LINE INDENT r = [ ] NEW_LINE first = 1 << ( N - 1 ) ; NEW_LINE last = first * 2 ; NEW_LINE for i in range ( last - 1 , first - 1 , - 1 ) : NEW_LINE INDENT zero_cnt = 0 ; NEW_LINE one_cnt = 0 ; NEW_LINE t = i ; NEW_LINE num_of_bits = 0 ; NEW_LINE while ( t ) : NEW_LINE INDENT if ( t & 1 ) : NEW_LINE INDENT one_cnt += 1 NEW_LINE DEDENT else : NEW_LINE INDENT zero_cnt += 1 NEW_LINE DEDENT num_of_bits += 1 NEW_LINE t = t >> 1 ; NEW_LINE DEDENT if ( one_cnt >= zero_cnt ) : NEW_LINE INDENT all_prefix_match = True ; NEW_LINE msk = ( 1 << num_of_bits ) - 2 ; NEW_LINE prefix_shift = 1 ; NEW_LINE while ( msk ) : NEW_LINE INDENT prefix = ( ( msk & i ) >> prefix_shift ) ; NEW_LINE prefix_one_cnt = 0 ; NEW_LINE prefix_zero_cnt = 0 ; NEW_LINE while ( prefix ) : NEW_LINE INDENT if ( prefix & 1 ) : NEW_LINE INDENT prefix_one_cnt += 1 NEW_LINE DEDENT else : NEW_LINE INDENT prefix_zero_cnt += 1 NEW_LINE DEDENT prefix = prefix >> 1 ; NEW_LINE DEDENT if ( prefix_zero_cnt > prefix_one_cnt ) : NEW_LINE INDENT all_prefix_match = False ; NEW_LINE break ; NEW_LINE DEDENT prefix_shift += 1 NEW_LINE msk = msk & ( msk << 1 ) ; NEW_LINE DEDENT if ( all_prefix_match ) : NEW_LINE INDENT r . append ( getBinaryRep ( i , num_of_bits ) ) ; NEW_LINE DEDENT DEDENT DEDENT return r NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 4 ; NEW_LINE results = NBitBinary ( n ) ; NEW_LINE for i in range ( len ( results ) ) : NEW_LINE INDENT print ( results [ i ] , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT