Count of N | Function to return the count of n - digit numbers that satisfy the given conditions ; DP array to store the pre - caluclated states ; Base cases ; i - digit numbers ending with 0 can be formed by concatenating 0 in the end of all the ( i - 1 ) - digit number ending at a non - zero digit ; i - digit numbers ending with non - zero can be formed by concatenating any non - zero digit in the end of all the ( i - 1 ) - digit number ending with any digit ; n - digit number ending with and ending with non - zero ; Driver code
def count_numbers ( k , n ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( 2 ) ] for i in range ( n + 1 ) ] NEW_LINE dp [ 1 ] [ 0 ] = 0 NEW_LINE dp [ 1 ] [ 1 ] = k - 1 NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = dp [ i - 1 ] [ 1 ] NEW_LINE dp [ i ] [ 1 ] = ( dp [ i - 1 ] [ 0 ] + dp [ i - 1 ] [ 1 ] ) * ( k - 1 ) NEW_LINE DEDENT return dp [ n ] [ 0 ] + dp [ n ] [ 1 ] NEW_LINE DEDENT k = 10 NEW_LINE n = 3 NEW_LINE print ( count_numbers ( k , n ) ) NEW_LINE