Count of numbers upto N digits formed using digits 0 to K | Python3 implementation to count the numbers upto N digits such that no two zeros are adjacent ; Function to count the numbers upto N digits such that no two zeros are adjacent ; Condition to check if only one element remains ; If last element is non zero , return K - 1 ; If last element is 0 ; Condition to check if value calculated already ; If last element is non zero , then two cases arise , current element can be either zero or non zero ; Memoize this case ; If last is 0 , then current can only be non zero ; Memoize and return ; Given N and K ; Function call
dp = [ [ 0 ] * 10 for j in range ( 15 ) ] NEW_LINE def solve ( n , last , k ) : NEW_LINE INDENT if ( n == 1 ) : NEW_LINE INDENT if ( last == k ) : NEW_LINE INDENT return ( k - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT return 1 NEW_LINE DEDENT DEDENT if ( dp [ n ] [ last ] ) : NEW_LINE INDENT return dp [ n ] [ last ] NEW_LINE DEDENT if ( last == k ) : NEW_LINE INDENT dp [ n ] [ last ] = ( ( k - 1 ) * solve ( n - 1 , k , k ) + ( k - 1 ) * solve ( n - 1 , 1 , k ) ) NEW_LINE return dp [ n ] [ last ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ n ] [ last ] = solve ( n - 1 , k , k ) NEW_LINE return dp [ n ] [ last ] NEW_LINE DEDENT DEDENT n = 2 NEW_LINE k = 3 NEW_LINE x = solve ( n , k , k ) + solve ( n , 1 , k ) NEW_LINE print ( x ) NEW_LINE