Count of numbers from range [ L , R ] whose sum of digits is Y | Set 2 | Javascript program for the above approach ; Function to find the sum of digits of numbers in the range [ 0 , X ] ; Check if count of digits in a number greater than count of digits in X ; Check Iif sum of digits of a number is equal to Y ; Check if current subproblem has already been computed ; Stores count of numbers whose sum of digits is Y ; Check if the number exceeds Y or not ; Iterate over all possible values of i - th digits ; Update res ; Return res ; Utility function to count the numbers in the range [ L , R ] whose sum of digits is Y ; Base Case ; Stores numbers in the form of its equivalent String ; Stores overlapping subproblems ; Initialize dp [ ] [ ] [ ] ; Stores count of numbers in the range [ 0 , R ] ; Update str ; Initialize dp [ ] [ ] [ ] ; Stores count of numbers in the range [ 0 , L - 1 ] ; Driver Code
let M = 1000 ; function cntNum ( X , i , sum , tight , dp ) { if ( i >= X . length sum < 0 ) { if ( sum == 0 ) { return 1 ; } return 0 ; } if ( dp [ sum ] [ i ] [ tight ] != - 1 ) { return dp [ sum ] [ i ] [ tight ] ; } let res = 0 ; let end = tight != 0 ? X [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) : 9 ; for ( let j = 0 ; j <= end ; j ++ ) { res += cntNum ( X , i + 1 , sum - j , ( tight > 0 & ( j == end ) ) == true ? 1 : 0 , dp ) ; } return dp [ sum ] [ i ] [ tight ] = res ; } function UtilCntNumRange ( L , R , Y ) { if ( R == 0 && Y == 0 ) { return 1 ; } let str = ( R ) . toString ( ) ; let dp = new Array ( M ) ; for ( let i = 0 ; i < M ; i ++ ) { dp [ i ] = new Array ( M ) ; for ( let j = 0 ; j < M ; j ++ ) { dp [ i ] [ j ] = new Array ( 2 ) ; for ( let k = 0 ; k < 2 ; k ++ ) dp [ i ] [ j ] [ k ] = - 1 ; } } let cntR = cntNum ( str , 0 , Y , 1 , dp ) ; str = ( L - 1 ) . toString ( ) ; for ( let i = 0 ; i < M ; i ++ ) { for ( let j = 0 ; j < M ; j ++ ) { for ( let k = 0 ; k < 2 ; k ++ ) dp [ i ] [ j ] [ k ] = - 1 ; } } let cntL = cntNum ( str , 0 , Y , 1 , dp ) ; return ( cntR - cntL ) ; } let L = 20 , R = 10000 , Y = 14 ; document . write ( UtilCntNumRange ( L , R , Y ) ) ;