Count of integers from the range [ 0 , N ] whose digit sum is a multiple of K | Javascript implementation of the approach ; To store the states of the dp ; Function to return the count of numbers from the range [ 0 , n ] whose digit sum is a multiple of k using bottom - up dp ; The digit in this index can only be from [ 0 , num [ idx ] ] ; The digit in this index can be anything from [ 0 , 9 ] ; new_tight is the flag value for the next position ; res can 't be negative ; Function to process the string to a vector of digits from MSD to LSD ; For large input number n ; Total number of digits in n ; Process the string to a vector of digits from MSD to LSD
var MAX = 100005 ; var MOD = 1000000007 ; var dp = Array . from ( Array ( MAX ) , ( ) => Array ( 101 ) ) ; for ( var i = 0 ; i < MAX ; i ++ ) for ( var j = 0 ; j < 101 ; j ++ ) dp [ i ] [ j ] = new Array ( 2 ) . fill ( - 1 ) ; function countNum ( idx , sum , tight , num , len , k ) { if ( len == idx ) { if ( sum == 0 ) return 1 ; else return 0 ; } if ( dp [ idx ] [ sum ] [ tight ] != - 1 ) return dp [ idx ] [ sum ] [ tight ] ; var res = 0 , limit ; if ( tight == 0 ) { limit = num [ idx ] ; } else { limit = 9 ; } for ( var i = 0 ; i <= limit ; i ++ ) { var new_tight = tight ; if ( tight == 0 && i < limit ) new_tight = 1 ; res += countNum ( idx + 1 , ( sum + i ) % k , new_tight , num , len , k ) ; res %= MOD ; } if ( res < 0 ) res += MOD ; return dp [ idx ] [ sum ] [ tight ] = res ; } function process ( s ) { var num = [ ] ; for ( var i = 0 ; i < s . length ; i ++ ) { num . push ( s [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ) ; } return num ; } var n = " " ; var len = n . length ; var k = 58 ; var num = process ( n ) ; document . write ( countNum ( 0 , 0 , 0 , num , len , k ) ) ;