**Approach 1**

This is the brute force approach. The algorithm is as follows:

- Iterate from i = L to i = R.
- Initialize the answer as 0.
- Calculate the sum of digits of ‘i’.
- If the sum of digits is equal to ‘Y’, increment the answer.
- Return answer.

Now let us implement the above approach in C++ programming language.

**Program**

```
#include <iostream>
using namespace std;
// Function to check if the sum of digits of X is equal to Y.
bool checkSumDigit(int x, int y)
{
int sum = 0;
// Calculating sum of digits of 'X'.
while (x > 0)
{
sum += x % 10;
x /= 10;
}
// Checking if the sum of digits is equal to 'Y'.
return (sum == y);
}
// Function that returns the count of numbers from the range [L, R] whose sum of Digits is Y.
int countNumbersY(int L, int R, int Y)
{
int answer = 0;
// Iterating from 'L' to 'R'.
for (int i = L; i <= R; i++)
{
// Checking if the sum of digits of 'i' is equal to 'Y'.
if (checkSumDigit(i, Y))
{
// If yes, increment the answer.
answer++;
}
}
return answer;
}
int main()
{
int L, R, Y;
cout << " Enter the Value of L, R, Y: ";
cin >> L >> R >> Y;
cout << "Count of numbers from the range [L, R] whose sum of digits is Y: " << countNumbersY(L, R, Y) << endl;
return 0;
}
```

**Input**

`Enter the value of L, R, Y: 10 100 7`

**Output**

`Count of numbers from the range [L, R] whose sum of digits is Y: 7`

**Time Complexity**

**O((log(R!) / (L-1)!)**, where **L** and **R** are the integer ranges.

The time complexity **checkSumDigit** Function is O(log X), and Since **checkSumDigit** Function is called for every value of between ‘L’ to ‘R’, So the Time Complexity of **checkNumberY** is.

T(L, R) = log(L) + log(L + 1) + log(L + 2) + . . . + log(R - 1) + log(R)

T(L, R) = [log(1) + log(2) + log(3) + . . . + log(R)] - [log(1) + log (2) + log(3) + . . . + log(L - 1)]

T(L, R) = log(1 * 2 * 3 * . . . * R) - log(1 * 2 * 3 * . . . * (L - 1))

T(L, R) = log(R!) - log((L - 1)!)

T(L, R) = log(R! / (L - 1)!)

**Space Complexity**

**O(1)**

We are only declaring a fixed number of variables. So it takes constant space.

**Approach 2**

Here we will use the concept of digit DP. Digit DP can be used to solve the problems where we need to query over a range. This problem falls into the category of digit DP. Please have a look at the __Digit DP__ blog. We first try to write a recursive solution to the problem and then try to apply digit DP to optimize it. We can choose from 0 to 9 for all three digits. That is, we will choose a digit for each position and then recurse for the other digits to build the sum equal to Y. Given below is the function definition.

`helper(i, sum, tight) = i=09 helper(i+1, (sum - i), tight(i == end))`

where sum denotes the total number of digits.

tight: Determine whether the total of the digits exceeds Y.

end: Stores the maximum potential value of a number's ith digit.

helper(N, Y, tight): Returns the number of numbers in the range [0, X] with a digit sum of Y.

Use DP to solve the problem by following the steps below.

- To compute and store the values of all subproblems of the aforementioned recurrence relation, create a 3D array called dp[N][Y][tight].
- Finally, dp[N][sum][tight] should be returned.

**Program**

```
#include <iostream>
#include <cstring>
using namespace std;
#define N 1000
// Function that counts the numbers in range 0 to STR whose sum of digits is SUM.
int helper(string str, int i, int sum, int tight, int dp[N][N][2])
{
// Check if count of digits in a number is
// greater than count of digits in str
if (i >= str.size() || sum < 0)
{
// If sum of digits of a
// number is equal to Y
if (sum == 0)
{
return 1;
}
return 0;
}
// Check if current subproblem has
// already been computed
if (dp[sum][i][tight] != -1)
{
return dp[sum][i][tight];
}
// Stores count of numbers whose
// sum of digits is Y
int ans = 0;
// Check if the number
// exceeds Y or not
int end = tight ? str[i] - '0' : 9;
// Iterate over all possible
// values of i-th digits
for (int j = 0; j <= end; j++)
{
// Update ans
ans += helper(str, i + 1, sum - j,
(tight & (j == end)), dp);
}
// Return ans
return dp[sum][i][tight] = ans;
}
// Function that returns the count of numbers from the range [L, R] whose sum of Digits is Y.
int countNumbersY(int L, int R, int Y)
{
if (R == 0 && Y == 0)
{
return 1;
}
// Stores numbers in the form
// of its equivalent string
string str = to_string(R);
// Stores overlapping subproblems
int dp[N][N][2];
// Initialize dp[][][]
memset(dp, -1, sizeof(dp));
// Stores count of numbers
// in the range [0, R]
int rightCount = helper(str, 0, Y,
true, dp);
// Update str
str = to_string(L - 1);
// Initialize dp[][][]
memset(dp, -1, sizeof(dp));
// Stores count of numbers in
// the range [0, L - 1]
int leftCount = helper(str, 0, Y,
true, dp);
return (rightCount - leftCount);
}
int main()
{
int L, R, Y;
cout << " Enter the Value of L, R, Y: ";
cin >> L >> R >> Y;
cout << "Count of numbers from the range [L, R] whose sum of digits is Y: " << countNumbersY(L, R, Y) << endl;
return 0;
}
```

**Input**

`Enter the value of L, R, Y: 20 70 10`

**Output**

`Count of numbers from the range [L, R] whose sum of digits is Y: 5`

**Time Complexity**

**O(Y * log(R)), **where ‘Y’ is the sum and ‘R’ is the Upper Bound.

**Space Complexity**

**O(Y * log(R)), **where ‘Y’ is the sum and ‘R’ is the Upper Bound.

Check out this problem - __Pair Sum In Array__.

**Also Read - **Strong number in c

**Key takeaways**

In this blog, we learned about a new problem namely the Count of numbers from the range [L, R] whose sum of digits is Y. We solved it using two different methods. The first method is Brute force and gives a time complexity of **O((log(R!) / (L-1)!). **The second approach used dynamic programming and gave a time complexity of **O(Y * log(R))**. Stay tuned for more such problems.