Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Problem Statement
3.
Approach 1
4.
Program
4.1.
Input
4.2.
Output
4.3.
Time Complexity
4.4.
Space Complexity
5.
Approach 2
6.
Program
6.1.
Input
6.2.
Output
6.3.
Time Complexity
6.4.
Space Complexity
7.
Key takeaways
Last Updated: Mar 27, 2024

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

Author Husen Kagdi
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction 

There will be a weekly contest this Sunday on the Leetcode platform. The tourist aka Gennady Korotkevich is preparing the problem statements for the contest. He thinks of a problem namely the count of numbers from the range [L, R] whose sum of digits is ‘Y’. Let us discuss the problem statement and the various approaches to solving the problem.

Problem Statement

Given two numbers ‘L’ and ‘R’, we need to find the count of numbers between ‘L’ and ‘R’, whose sum of digits is ‘Y’.

For Example:

L = 10, R = 100, Y = 7

Then the numbers whose sum of digits is 7 and lie between L and R are:

16 25 34 43 52 61 70

So, there are 7 such numbers. Therefore the output is 7.

Also see, Euclid GCD Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 1

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

  1. Iterate from i = L to i = R.
  2. Initialize the answer as 0.
  3. Calculate the sum of digits of ‘i’.
  4. If the sum of digits is equal to ‘Y’, increment the answer.
  5. 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.

  1. To compute and store the values of all subproblems of the aforementioned recurrence relation, create a 3D array called dp[N][Y][tight]. 
  2. 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.

Previous article
Count of Numbers in the range [L, R] Whose Sum Of Digits is Y
Next article
Find Count of numbers from a given range whose product of digits is X
Live masterclass