Count of numbers from range [ L , R ] whose sum of digits is Y | Set 2 | CPP 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 ; If 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define M  1000 NEW_LINE int cntNum ( string X , int i , int sum , int tight , int dp [ M ] [ M ] [ 2 ] ) { 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 ? X [ i ] - '0' : 9 ; for ( int j = 0 ; j <= end ; j ++ ) { res += cntNum ( X , i + 1 , sum - j , ( tight & ( j == end ) ) , dp ) ; } return dp [ sum ] [ i ] [ tight ] = res ; } int UtilCntNumRange ( int L , int R , int Y ) { if ( R == 0 && Y == 0 ) { return 1 ; } string str = to_string ( R ) ; int dp [ M ] [ M ] [ 2 ] ; memset ( dp , -1 , sizeof ( dp ) ) ; int cntR = cntNum ( str , 0 , Y , true , dp ) ; str = to_string ( L - 1 ) ; memset ( dp , -1 , sizeof ( dp ) ) ; int cntL = cntNum ( str , 0 , Y , true , dp ) ; return ( cntR - cntL ) ; } int main ( ) { int L = 20 , R = 10000 , Y = 14 ; cout << UtilCntNumRange ( L , R , Y ) ; }