Count of numbers from range [ L , R ] whose sum of digits is Y | Set 2 | Java 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
import java . util . * ; class GFG { static final int M = 1000 ; static int cntNum ( String X , int i , int sum , int tight , int 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 ] ; } int res = 0 ; int end = tight != 0 ? X . charAt ( i ) - '0' : 9 ; for ( int 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 ; } static int UtilCntNumRange ( int L , int R , int Y ) { if ( R == 0 && Y == 0 ) { return 1 ; } String str = String . valueOf ( R ) ; int [ ] [ ] [ ] dp = new int [ M ] [ M ] [ 2 ] ; for ( int i = 0 ; i < M ; i ++ ) { for ( int j = 0 ; j < M ; j ++ ) { for ( int k = 0 ; k < 2 ; k ++ ) dp [ i ] [ j ] [ k ] = - 1 ; } } int cntR = cntNum ( str , 0 , Y , 1 , dp ) ; str = String . valueOf ( L - 1 ) ; for ( int i = 0 ; i < M ; i ++ ) { for ( int j = 0 ; j < M ; j ++ ) { for ( int k = 0 ; k < 2 ; k ++ ) dp [ i ] [ j ] [ k ] = - 1 ; } } int cntL = cntNum ( str , 0 , Y , 1 , dp ) ; return ( cntR - cntL ) ; } public static void main ( String [ ] args ) { int L = 20 , R = 10000 , Y = 14 ; System . out . print ( UtilCntNumRange ( L , R , Y ) ) ; } }