Count possible N | DP array for memoization ; Utility function to count N digit numbers with digit i not appearing more than max_digit [ i ] consecutively ; If number with N digits is generated ; Create a reference variable ; Check if the current state is already computed before ; Initialize ans as zero ; Check if count of previous digit has reached zero or not ; Fill current position only with digits that are unequal to previous digit ; Else set the value of count for this new digit accordingly from max_digit [ ] ; Function to count N digit numbers with digit i not appearing more than max_digit [ i ] consecutive times ; Stores the final count ; Print the total count ; Driver Code ; Function Call
dp = [ [ [ - 1 for i in range ( 5005 ) ] for i in range ( 12 ) ] for i in range ( 12 ) ] NEW_LINE def findCountUtil ( N , maxDigit , position , previous , count ) : NEW_LINE INDENT global dp NEW_LINE if ( position == N ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT ans = dp [ position ] [ previous ] [ count ] NEW_LINE if ( ans != - 1 ) : NEW_LINE INDENT return ans NEW_LINE DEDENT ans = 0 NEW_LINE for i in range ( 10 ) : NEW_LINE INDENT if ( count == 0 and previous != i ) : NEW_LINE INDENT ans = ( ans + ( findCountUtil ( N , maxDigit , position + 1 , i , maxDigit [ i ] - 1 ) ) % 1000000007 ) % 1000000007 NEW_LINE DEDENT elif ( count != 0 ) : NEW_LINE INDENT ans = ( ans + ( findCountUtil ( N , maxDigit , position + 1 , i , count - 1 if ( previous == i and position != 0 ) else maxDigit [ i ] - 1 ) ) % 1000000007 ) % 1000000007 NEW_LINE DEDENT DEDENT dp [ position ] [ previous ] [ count ] = ans NEW_LINE return ans NEW_LINE DEDENT def findCount ( N , maxDigit ) : NEW_LINE INDENT ans = findCountUtil ( N , maxDigit , 0 , 0 , 1 ) NEW_LINE print ( ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 2 NEW_LINE maxDigit = [ 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ] NEW_LINE findCount ( N , maxDigit ) NEW_LINE DEDENT