Count possible N | Macros for modulus ; 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
let MOD = 1000000007 ; let dp = new Array ( 5005 ) ; for ( let i = 0 ; i < 12 ; i ++ ) { dp [ i ] = new Array ( 12 ) ; for ( let j = 0 ; j < 12 ; j ++ ) { dp [ i ] [ j ] = new Array ( 12 ) ; for ( let k = 0 ; k < 12 ; k ++ ) { dp [ i ] [ j ] [ k ] = - 1 ; } } } function findCountUtil ( N , maxDigit , position , previous , count ) { if ( position == N ) { return 1 ; } let ans = dp [ position ] [ previous ] [ count ] ; if ( ans != - 1 ) { return ans ; } ans = 0 ; for ( let i = 0 ; i <= 9 ; ++ i ) { if ( count == 0 && previous != i ) { ans = ( ans + ( findCountUtil ( N , maxDigit , position + 1 , i , maxDigit [ i ] - 1 ) ) % MOD ) % MOD ; } else if ( count != 0 ) { ans = ( ans + ( findCountUtil ( N , maxDigit , position + 1 , i , ( previous == i && position != 0 ) ? count - 1 : maxDigit [ i ] - 1 ) ) % MOD ) % MOD ; } } return ans ; } function findCount ( N , maxDigit ) { let position = 0 ; let previous = 0 ; let count = 1 ; let ans = findCountUtil ( N , maxDigit , position , previous , count ) ; document . write ( ans ) ; } let N = 2 ; let maxDigit = [ 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ] ; findCount ( N , maxDigit ) ;