Count of integers up to N which represent a Binary number | Function to return the count ; PreCompute and store the powers of 2 ; If the current last digit is 1 ; Add 2 ^ ( ctr - 1 ) possible integers to the answer ; If the current digit exceeds 1 ; Set answer as 2 ^ ctr - 1 as all possible binary integers with ctr number of digits can be obtained ; Driver code
def countBinaries ( N ) : NEW_LINE INDENT powersOfTwo = [ 0 ] * 11 NEW_LINE powersOfTwo [ 0 ] = 1 NEW_LINE for i in range ( 1 , 11 ) : NEW_LINE INDENT powersOfTwo [ i ] = powersOfTwo [ i - 1 ] * 2 NEW_LINE DEDENT ctr = 1 NEW_LINE ans = 0 NEW_LINE while ( N > 0 ) : NEW_LINE INDENT if ( N % 10 == 1 ) : NEW_LINE INDENT ans += powersOfTwo [ ctr - 1 ] NEW_LINE DEDENT elif ( N % 10 > 1 ) : NEW_LINE INDENT ans = powersOfTwo [ ctr ] - 1 NEW_LINE DEDENT ctr += 1 NEW_LINE N = N // 10 NEW_LINE DEDENT return ans NEW_LINE DEDENT N = 20 NEW_LINE print ( countBinaries ( N ) ) NEW_LINE