Count the numbers with N digits and whose suffix is divisible by K | Javascript implementation to Count the numbers with N digits and whose suffix is divisible by K ; Suffix of length pos with remainder rem and Z representing whether the suffix has a non zero digit until now ; Base case ; If count of digits is less than n ; Placing all possible digits in remaining positions ; If remainder non zero and suffix has n digits ; If the subproblem is already solved ; Placing all digits at MSB of suffix and increasing it 's length by 1 ; Non zero digit is placed ; Store and return the solution to this subproblem ; Function to Count the numbers with N digits and whose suffix is divisible by K ; Since we need powers of 10 for counting , it 's better to  pre store them along with their  modulo with 1e9 + 7 for counting ; Since at each recursive step we increase the suffix length by 1 by placing digits at its leftmost position , we need powers of 10 modded with k , in order to fpos the new remainder efficiently ; Driver Code
var mod = 1000000007 ; var dp = Array . from ( Array ( 1005 ) , ( ) => Array ( 105 ) ) ; for ( var i = 0 ; i < 1005 ; i ++ ) { for ( var j = 0 ; j < 105 ; j ++ ) { dp [ i ] [ j ] = Array ( 2 ) . fill ( - 1 ) ; } } var powers = Array ( 1005 ) ; var powersModk = Array ( 1005 ) ; function calculate ( pos , rem , z , k , n ) { if ( rem == 0 && z ) { if ( pos != n ) return ( powers [ n - pos - 1 ] * 9 ) % mod ; else return 1 ; } if ( pos == n ) return 0 ; if ( dp [ pos ] [ rem ] [ z ] != - 1 ) return dp [ pos ] [ rem ] [ z ] ; var count = 0 ; for ( var i = 0 ; i < 10 ; i ++ ) { if ( i == 0 ) count = ( count + ( calculate ( pos + 1 , ( rem + ( i * powersModk [ pos ] ) % k ) % k , z , k , n ) ) ) % mod ; else count = ( count + ( calculate ( pos + 1 , ( rem + ( i * powersModk [ pos ] ) % k ) % k , 1 , k , n ) ) ) % mod ; } return dp [ pos ] [ rem ] [ z ] = count ; } function countNumbers ( n , k ) { var st = 1 ; for ( var i = 0 ; i <= n ; i ++ ) { powers [ i ] = st ; st *= 10 ; st %= mod ; } st = 1 ; for ( var i = 0 ; i <= n ; i ++ ) { powersModk [ i ] = st ; st *= 10 ; st %= mod ; } return calculate ( 0 , 0 , 0 , k , n ) ; } var N = 2 ; var K = 2 ; document . write ( countNumbers ( N , K ) ) ;