Table of contents

Introduction

Problem Statement

Approach 1

Program

4.1.

Input

4.2.

Output

4.3.

Time Complexity

4.4.

Space Complexity

Approach 2

Program

6.1.

Input

6.2.

Output

6.3.

Time Complexity

6.4.

Space Complexity

Key Takeaways

Last Updated: Mar 27, 2024

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

Author Husen Kagdi

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 thoughts 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 solve the problem.

Problem Statement

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

For Example:

L=10, R=100, Y=7

Then the numbers whose sum of digits is 7 and lies 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

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 it in the C++ programming language.

Program

#include<iostream>
using namespace std;
bool check(int x, int y){
int sum=0;

// Calculating sum of digits of x.
while(x>0){
sum+=x%10;
x/=10;
}

// Checking if sum of digits is equal to y.
return (sum==y);
}
int helper(int L, int R, int Y){
int answer = 0;

// Iterating from L to R.
for(int i=L; i<=R; i++){

  // Checking if sum of digits of i is equal to Y.
  if(check(i,Y)){

  // If yes, increment the answer.
answer++;
}
}
return answer;

}
int main(){
int L, R, Y;
cin>>L>>R>>Y;

cout<<helper(L, R, Y);
return 0;
}

Input

10 100 7

Output

Time Complexity

O((R - L) * log(R))

We are iterating from L and R and checking if the sum of digits of the iterator is equal to Y or not. The checking function takes O(log(R)) time in the worst case. The number is reduced to 1 by repeatedly dividing by 10. So it takes O( log(R) ) time.

Space Complexity

O(1)

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

Approach 2

cntNum(i, sum, tight) = i=09 cntNum(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.

cntNum(N, Y, tight): cntNum(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<bits/stdc++.h>
using namespace std;

#define N 1000

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;
}

int count(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;
cin >> L >> R >> Y;
cout << count(L, R, Y);
return 0;
}

Input

10 100 7

Output

Time Complexity

O( Y * log(R))

Space Complexity

O( Y * log(R))

Check out this problem - Subarray Sum Divisible By K

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((R - L+1) * log(R)). Second approach used dynamic programming and gave a time complexity of O(Y * log(R)). Stay tuned for more such problems.

Happy Coding!

Live masterclass

Land an SDE Role at Google: Master DSA the smart way

by Saurav Prateek, SDE2@Google

19 Sep, 2024

01:30 PM

38+ registered

Become a Data Analyst at MAANG: Learn PowerBI for Data visualization

by Megna Roy, Senior Data Analyst @Amazon

17 Sep, 2024

01:30 PM

281+ registered

Learn Advanced Excel: Ace Data Analytics Interview

by Megna Roy, Data Analyst @ Amazon

15 Sep, 2024

06:30 AM

3857+ registered

Land an SDE Role at Google: Master DSA the smart way

by Saurav Prateek, SDE2@Google

19 Sep, 2024

01:30 PM

38+ registered

Become a Data Analyst at MAANG: Learn PowerBI for Data visualization

by Megna Roy, Senior Data Analyst @Amazon

17 Sep, 2024

01:30 PM

281+ registered

View more events