Find the numbers from 1 to N that contains exactly k non | Function to find number less than N having k non - zero digits ; Store the memorised values ; Initialise ; Base ; Calculate all states For every state , from numbers 1 to N , the count of numbers which contain exactly j non zero digits is being computed and updated in the dp array . ; Return the required answer ; Driver code ; Function call
def k_nonzero_numbers ( s , n , k ) : NEW_LINE INDENT dp = [ [ [ 0 for i in range ( k + 2 ) ] for i in range ( 2 ) ] for i in range ( n + 2 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT for j in range ( 2 ) : NEW_LINE INDENT for x in range ( k + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] [ x ] = 0 NEW_LINE DEDENT DEDENT DEDENT dp [ 0 ] [ 0 ] [ 0 ] = 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT sm = 0 NEW_LINE while ( sm < 2 ) : NEW_LINE INDENT for j in range ( k + 1 ) : NEW_LINE INDENT x = 0 NEW_LINE y = 0 NEW_LINE if sm : NEW_LINE INDENT y = 9 NEW_LINE DEDENT else : NEW_LINE INDENT y = ord ( s [ i ] ) - ord ( '0' ) NEW_LINE DEDENT while ( x <= y ) : NEW_LINE INDENT dp [ i + 1 ] [ ( sm or x < ( ord ( s [ i ] ) - ord ( '0' ) ) ) ] [ j + ( x > 0 ) ] += dp [ i ] [ sm ] [ j ] NEW_LINE x += 1 NEW_LINE DEDENT DEDENT sm += 1 NEW_LINE DEDENT DEDENT return dp [ n ] [ 0 ] [ k ] + dp [ n ] [ 1 ] [ k ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT s = "25" NEW_LINE k = 2 NEW_LINE n = len ( s ) NEW_LINE print ( k_nonzero_numbers ( s , n , k ) ) NEW_LINE DEDENT