Count N digits numbers with sum divisible by K | JavaScript Program to implement the above approach ; Function to count the N digit numbers whose sum is divisible by K ; Base case ; If already computed subproblem occurred ; Store the count of N digit numbers whose sum is divisible by K ; Check if the number does not contain any leading 0. ; Recurrence relation ; Driver Code ; Stores the values of overlapping subproblems
var M = 1000 ; function countNum ( N , sum , K , st , dp ) { if ( N == 0 && sum == 0 ) { return 1 ; } if ( N < 0 ) { return 0 ; } if ( dp [ N ] [ sum ] [ st ] != - 1 ) { return dp [ N ] [ sum ] [ st ] ; } var res = 0 ; var start = st == 1 ? 0 : 1 ; for ( var i = start ; i <= 9 ; i ++ ) { res += countNum ( N - 1 , ( sum + i ) % K , K , ( st i > 0 ) , dp ) ; } return dp [ N ] [ sum ] [ st ] = res ; } var N = 2 , K = 7 ; var dp = Array . from ( Array ( M ) , ( ) => Array ( M ) ) ; for ( var i = 0 ; i < M ; i ++ ) for ( var j = 0 ; j < M ; j ++ ) dp [ i ] [ j ] = new Array ( 2 ) . fill ( - 1 ) ; document . write ( countNum ( N , 0 , K , 0 , dp ) ) ;