Count of numbers between range having only non | JavaScript implementation of the approach ; states - position , sum , rem , tight sum can have values upto 162 , if we are dealing with numbers upto 10 ^ 18 when all 18 digits are 9 , then sum is 18 * 9 = 162 ; n is the sum of digits and number should be divisible by m ; Function to return the count of required numbers from 0 to num ; Last position ; If this result is already computed simply return it ; Maximum limit upto which we can place digit . If tight is 1 , means number has already become smaller so we can place any digit , otherwise num [ pos ] ; If the current digit is zero and nonz is 1 , we can 't place it ; Function to convert x into its digit vector and uses count ( ) function to return the required count ; Initialize dp ; Driver code
var M = 20 ; var dp = Array . from ( Array ( M ) , ( ) => Array ( 165 ) ) ; var n , m ; function count ( pos , sum , rem , tight , nonz , num ) { if ( pos == num . length ) { if ( rem == 0 && sum == n ) return 1 ; return 0 ; } if ( dp [ pos ] [ sum ] [ rem ] [ tight ] != - 1 ) return dp [ pos ] [ sum ] [ rem ] [ tight ] ; var ans = 0 ; var limit = ( tight ? 9 : num [ pos ] ) ; for ( var d = 0 ; d <= limit ; d ++ ) { if ( d == 0 && nonz ) continue ; var currSum = sum + d ; var currRem = ( rem * 10 + d ) % m ; var currF = ( tight != 0 || ( d < num [ pos ] ) ) ? 1 : 0 ; ans += count ( pos + 1 , currSum , currRem , currF , ( nonz != 0 d != 0 ) ? 1 : 0 , num ) ; } dp [ pos ] [ sum ] [ rem ] [ tight ] = ans ; return ans ; } function solve ( x ) { var num = [ ] ; while ( x ) { num . push ( x % 10 ) ; x = parseInt ( x / 10 ) ; } num . reverse ( ) ; for ( var i = 0 ; i < M ; i ++ ) for ( var j = 0 ; j < 165 ; j ++ ) dp [ i ] [ j ] = Array . from ( Array ( M ) , ( ) => Array ( 2 ) . fill ( - 1 ) ) ; return count ( 0 , 0 , 0 , 0 , 0 , num ) ; } var L = 1 , R = 100 ; n = 8 , m = 2 ; document . write ( solve ( R ) - solve ( L ) ) ;