Range problems are an essential topic for programming interviews. Various important algorithms and tricks are present which can solve range problems. This blog will discuss the problem of counting the numbers in the range [L, R] whose sum of digits is Y.

Before diving into the solution, let’s take a closer look at the problem statement once again.

Problem Statement

Given three positive integers L, R, and Y. The main task is to count the numbers in the range [L, R] whose sum of digits is equal to Y.

Note: The range [L, R] is inclusive of L and R, i.e., L and R are included in the range.

Input

L = 100, R = 150, Y = 10

Output

5

Explanation

There are five numbers between L = 100 and R = 150 whose digits sum to Y = 10.

We have the following valid numbers:

109 whose sum of digits = 1 + 0 + 9 = 10

118 whose sum of digits = 1 + 1 + 8 = 10

127 whose sum of digits = 1 + 2 + 7 = 10

136 whose sum of digits = 1 + 3 + 6 = 10

145 whose sum of digits = 1 + 4 + 5 = 10

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

Brute Force Approach

This is the most obvious and very simple approach is that we iterate over all the numbers between L and R and then check if the sum of digits equals Y or not for each number.

Algorithm

Call the corresponding ‘count_numbers()’ function to count the numbers in the range [L, R] whose sum of digits is Y.

Initialize a variable ‘total’ for storing the count of the numbers.

Iterate using a for loop from L to R; for each number, check whether it has a sum of digits equal to Y or not using the ‘valid()’ function.

For each number, find the sum of all its digits.

This can be done by maintaining a while-loop until the number >0 and, inside the while-loop, keep adding the last digit (number%10) and then decrementing the number each time by dividing it with 10(number = number /10).

If the sum equals Y, then return 1; else, return 0.

Dry Run

We will iterate from L to R, and for each number, we will count the sum of the digits.

Iteration 1: Number to check = 100

Steps to calculate the sum of digits in the number-

The given number looks like this.

Extract the last digit of the number by taking modulo by 10 and then dividing the number by 10.

Add the last digit 0 to the variable ‘sum’, which now has the value 0. After dividing by 10, the number looks like this

Extract the last digit of the number by taking modulo by 10 and then dividing the number by 10.

Add the last digit 0 to the variable ‘sum’, which now has the value 0. After dividing by 10, the number looks like this

Extract the last digit of the number by taking modulo by 10 and then dividing the number by 10.

Add the last digit 1 to the variable ‘sum’ which now has the value 1. The number now has a zero value, so there will be no more iterations.

100 has the sum of digits = 1 which is not equal to Y = 10.

Similarly, we will calculate the sum of digits from 101 to 150, and the numbers with the sum of digits equal to 10 which are 109, 118, 127, 136, and 145 will be added to the answer.

Implementation in C++

#include <iostream>
using namespace std;
/*
Function for checking whether the sum
of digits is equal to Y or not
*/
bool valid(int num, int Y){
// Storing the sum of digits
int sum = 0;
while (num > 0){
sum += (num % 10);
num /= 10;
}
return (sum == Y);
}
/*
Function to find the count
of numbers in the range [L, R] whose sum of digits equals Y
*/
int count_numbers(int L, int R, int Y){
// Storing total numbers
int total = 0;
for (int i = L; i <= R; i++){
if (valid(i, Y)){
++total;
}
}
// Returning the count
return total;
}
// Driver Code
int main(){
// Given values of L, R and Y
int L = 100, R = 150, Y = 10;
// Calling the function and displaying the output
cout << count_numbers(L, R, Y);
}

Output

Implementation in Java

public class MyClass {
/*
Function for checking whether the sum
of digits is equal to Y or not
*/
static boolean valid(int num, int Y){
// Storing the sum of digits
int sum=0;
while(num>0){
sum+=(num%10);
num/=10;
}
return (sum==Y);
}
/*
Function to find the count
of numbers in the range [L, R] whose sum of digits equals Y
*/
static int count_numbers(int L, int R, int Y){
// Storing total numbers
int total=0;
for(int i = L; i <= R; i++){
if(valid(i,Y)){
++total;
}
}
// Returning the count
return total;
}
// Driver Function
public static void main(String args[]) {
// Given values of L, R and Y
int L = 100, R = 150, Y = 10;
// Calling the function and displaying the output
System.out.print(count_numbers(L, R, Y));
}
}

Output

Time Complexity

O((R - L + 1)*log_{10}R)

Explanation: There are (R - L + 1) numbers in the range [L, R], and for each number, we iterate through all its digits. Since a number ‘N’ has a log_{10}N number of digits and the maximum value of N can be R as the given range is [L, R], so considering the worst-case, overall complexity is O((R - L + 1)*log_{10}R).

Space Complexity

O(1)

Explanation: Since we have only used a few variables that take a constant space of O(1).

Recursion Approach

If we look at the above solution carefully, we observe that we can also proceed in the reverse order. Thus, we can generate the numbers that follow the condition that the sum of all digits is Y.

Algorithm

Define a recursive function, such as count_numbers(idx, sum, s, tight), where idx is the current index of the number and denotes the current place of the number. “sum” stores the remaining sum that is left to make sum equal to ‘Y’. The variable ‘s’ corresponds to the string which is the maximum number limit up to which we have to calculate. The ‘tight’ variable stores whether the current number formed is equal to the starting (idx+1) characters. The function returns the total count of numbers ranging from 0 to ‘max_num’ such that the sum of digits is “sum”.

Note: Since we need to find the count of numbers in the range [L, R], we compute the count of such numbers, say CountR, from 0 to ‘R’ and say CountL, from 0 to ‘L-1’. Then the required answer will be (CountR - CountL).

If the sum equals zero, the current sum is equal to Y, so simply return value one here.

If “sum”<0 or idx>= s.length(), then there can be no possible answer, and we return 0. This serves as our base case for the recursive function.

Now, from here, two cases arise:

If the tight variable is positive or true, then the current digit that we can pick must lie within the range from 0 to (s[idx] - ‘0’); otherwise, it will be greater than the maximum number that is allowed to pick. Call the recursive function ‘count_numbers()’ after adding each digit.

If the tight variable is zero or false, then the current digit that we can pick must lie within the range from 0 to 9; as we can pick any digit, the number will still be less than the maximum number allowed to pick. Call the recursive function ‘count_numbers()’ after adding each digit.1

Display the output as the difference between CountR and CountL.

Dry Run

The main part of the approach is to understand the recursive function. The recursive function for ‘x’ returns all the integers from the range 0 to ‘x’ which have the sum of digits equal to Y. If we do know how to implement the recursive function then the answer is simply the

Value of the recursive function( R ) - Value of the recursive function( L - 1 )

Now, let’s take a look at the recursion tree of the function when calculated for value R which looks like this.

Initially, the recursive function is called for ‘idx’ = 0, sum = Y =10, string s=”150” and tight = 1. Now as the tight is equal to 1 initially, the possible digits at ‘idx’ = 0 will be 0 and 1. At ‘idx’ = 0 when digit = 0 is taken the tight becomes false as it is less than the value at s[idx] and when digit = 1 is taken the tight becomes true as the value is equal to the s[idx]. In this way, we iterate through each possibility for given idx, sum, string s, and tight values. The base cases are when the sum is equal to zero which means we have formed a sum equal to Y so we will return 1 from there. Other base cases include when sum is less than zero or index ‘idx’ is greater than or equal to string size. In both cases, we will return zero.

Let’s take a look at the implementation of the above idea in code.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
/*
Function to find the sum of the digits
Of numbers in the range [0, max_num]
*/
int count_numbers(int idx, int sum, string s, int tight){
// If sum left is equal to zero return 1
if (sum == 0){
return 1;
}
// Base Case
if (idx >= s.length() || sum < 0){
return 0;
}
// Storing the count of numbers whose sum of digits = Y
int ans = 0;
if (tight){
// When tight variable is true
for (int i = 0; i <= (s[idx] - '0'); i++){
if (i == s[idx] - '0'){
ans += count_numbers(idx + 1, sum - i, s, 1);
}
else{
ans += count_numbers(idx + 1, sum - i, s, 0);
}
}
}
else{
// When tight variable is false
for (int i = 0; i <= 9; i++){
ans += count_numbers(idx + 1, sum - i, s, 0);
}
}
// Return the total count
return ans;
}
// Driver Code
int main(){
// Given values of L, R and Y
int L = 100, R = 150, Y = 10;
// Converting numbers to strings
string l = to_string(L - 1);
string r = to_string(R);
// Calling the function and displaying the output
int CountR = count_numbers(0, Y, r, 1);
int CountL = count_numbers(0, Y, l, 1);
cout << CountR - CountL;
}

Output

Implementation in Java

public class MyClass{
/*
Function to find the sum of the digits
Of numbers in the range [0, max_num]
*/
static int count_numbers(int idx, int sum, String s, int tight){
// If sum left is equal to zero return 1
if (sum == 0){
return 1;
}
// Base Case
if (idx >= s.length() || sum < 0){
return 0;
}
// Storing the count of numbers whose sum of digits = Y
int ans = 0;
if (tight > 0){
// When tight variable is true
for (int i = 0; i <= (s.charAt(idx) - '0'); i++){
if (i == s.charAt(idx) - '0'){
ans += count_numbers(idx + 1, sum - i, s, 1);
}
else{
ans += count_numbers(idx + 1, sum - i, s, 0);
}
}
}
else{
// When tight variable is false
for (int i = 0; i <= 9; i++){
ans += count_numbers(idx + 1, sum - i, s, 0);
}
}
// Return the total count
return ans;
}
// Driver Function
public static void main(String args[]){
// Given values of L, R and Y
int L = 100, R = 150, Y = 10;
// Converting numbers to strings
String l = String.valueOf(L - 1);
String r = String.valueOf(R);
// Calling the function and displaying the output
int CountR = count_numbers(0, Y, r, 1);
int CountL = count_numbers(0, Y, l, 1);
System.out.print(CountR - CountL);
}
}

Output

Time Complexity

O(10^{(max(logR, Y))})

Explanation: At each recursion call, there are 10 possibilities of keeping a digit at the current index ‘idx’ and this process can go up upto max(log R, Y) times in the recursion. Hence, the time complexity of the recursive approach is O(10^{(max(logR, Y))}).

Space Complexity

O(10^{(max(logR, Y))})

Explanation: Following the above reasoning, the recursion tree will be generated, and many such recursive calls will be made in a recursion stack that accounts for space complexity. And the number of recursive calls is O(10^{(max(logR, Y))}).

Dynamic Programming Approach

If we look at the above solution carefully, we can observe repeated subproblems. We had to keep in mind that whenever we encounter repeated subproblems in recursion, we can further optimize the solution through dynamic optimization.

Since we have three variables in the recursive function, to keep track of states, we need to create a 3D DP array to store the results, and if the results are called once again, we will save a recursion call and directly return from the DP array.

Algorithm

Define a recursive function, such as count_numbers(idx, sum, s, tight), where ‘idx’ is the current index of the number and denotes the current place of the number. “sum” stores the remaining sum that is left to make sum equal to Y. The variable ‘s’ corresponds to the string which is the maximum number limit upto which we have to calculate. The ‘tight’ variable stores whether the current number formed is equal to the starting (idx+1) characters or not. The function returns the total count of numbers ranging from 0 to max_num such that the sum of digits is “sum”.

Note: Since we need to find the count of numbers in the range [L, R], we compute the count of such numbers, say CountR, from 0 to ‘R’ and say CountL, from 0 to ‘L-1’. Then the required answer will be (CountR - CountL).

If the ‘count_numbers()’ function is calculated for constraints idx, sum, and tight then simply return the value from the dp array.

If the sum equals zero, the current sum is equal to Y, so simply return value one here.

If “sum”<0 or idx>= s.length(), then there can be no possible answer, and we return 0. This serves as our base case for the recursive function.

Now, from here, two cases arise:

If the ‘tight’ variable is positive or true, then the current digit that we can pick must lie within the range from 0 to (s[idx] - ‘0’); otherwise, it will be greater than the maximum number that is allowed to pick. Call the recursive function ‘count_numbers()’ after adding each digit and add for all the calls in the ‘ans.’

If the ‘tight’ variable is zero or false, then the current digit that we can pick must lie within the range from 0 to 9; as we can pick any digit, the number will still be less than the maximum number allowed to pick. Call the recursive function ‘count_numbers()’ after adding each digit and add for all the calls in the ‘ans’.

Store the result in the corresponding dp array and return the variable ‘ans’ as the total count of numbers less than string ‘s’.

Display the output as the difference between CountR and CountL.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
int dp[11][101][2];
/*
Function to find the sum of digits
Of numbers in the range [0, max_num]
*/
int count_numbers(int idx, int sum, string s, int tight){
// If sum left is equal to zero return 1
if (sum == 0){
return 1;
}
// Base Case
if (idx >= s.length() || sum < 0){
return 0;
}
// Return the value if already calculated
if (dp[idx][sum][tight] != -1){
return dp[idx][sum][tight];
}
// Storing the count of numbers whose sum of digits = Y
int ans = 0;
if (tight){
// When tight variable is true
for (int i = 0; i <= (s[idx] - '0'); i++){
if (i == s[idx] - '0'){
ans += count_numbers(idx + 1, sum - i, s, 1);
}
else{
ans += count_numbers(idx + 1, sum - i, s, 0);
}
}
}
else{
// When tight variable is false
for (int i = 0; i <= 9; i++){
ans += count_numbers(idx + 1, sum - i, s, 0);
}
}
// Return the total count
return dp[idx][sum][tight] = ans;
}
// Driver Code
int main(){
// Given values of L, R and Y
int L = 100, R = 150, Y = 10;
// Converting numbers to strings
string l = to_string(L - 1);
string r = to_string(R);
// Calling the function and displaying the output
memset(dp, -1, sizeof(dp));
int CountR = count_numbers(0, Y, r, 1);
memset(dp, -1, sizeof(dp));
int CountL = count_numbers(0, Y, l, 1);
cout << CountR - CountL;
}

Output

Implementation in Java

public class MyClass{
static int dp[][][] = new int[11][101][2];
/*
Function to find the sum of digits
Of numbers in the range [0, max_num]
*/
static int count_numbers(int idx, int sum, String s, int tight){
// If sum left is equal to zero return 1
if (sum == 0){
return 1;
}
// Base Case
if (idx >= s.length() || sum < 0){
return 0;
}
// Return the value if already calculated
if (dp[idx][sum][tight] != -1){
return dp[idx][sum][tight];
}
// Storing the count of numbers whose sum of digits = Y
int ans = 0;
if (tight > 0){
// When tight variable is true
for (int i = 0; i <= (s.charAt(idx) - '0'); i++){
if (i == s.charAt(idx) - '0'){
ans += count_numbers(idx + 1, sum - i, s, 1);
}
else{
ans += count_numbers(idx + 1, sum - i, s, 0);
}
}
}
else{
// When tight variable is false
for (int i = 0; i <= 9; i++){
ans += count_numbers(idx + 1, sum - i, s, 0);
}
}
// Return the total count
return dp[idx][sum][tight] = ans;
}
// Driver Function
public static void main(String args[])
{
// Given values of L, R and Y
int L = 100, R = 150, Y = 10;
// Converting numbers to strings
String l = String.valueOf(L - 1);
String r = String.valueOf(R);
// Calling the function and displaying the output
for (int i = 0; i <= 10; i++){
for (int j = 0; j <= 100; j++){
dp[i][j][0] = dp[i][j][1] = -1;
}
}
int CountR = count_numbers(0, Y, r, 1);
for (int i = 0; i <= 10; i++){
for (int j = 0; j <= 100; j++){
dp[i][j][0] = dp[i][j][1] = -1;
}
}
int CountL = count_numbers(0, Y, l, 1);
System.out.print(CountR - CountL);
}
}

Output

Time Complexity

O(Y * log_{10}(R) * 10) where Y is the sum of digits required and R is the right limit of the range.

Explanation: At each recursive call, we will make a total of 10 possible iterations of digits 0 to 9. The maximum number of digits in the string can be log_{10}(R), and the worst case limit up to which we will calculate the sum is Y(sum of the digits). The cumulative effect of these three things gives a time complexity of O(Y * log_{10}(R) * 10).

Space Complexity

O(Y * log_{10}(R) * 2) where Y is the sum of digits required and R is the right limit of the range.

Explanation: Since we only need a dp array at max size (Y * log_{10}R * 2).

How to convert the recursive solution to a dynamic approach-based solution?

In the recursive solution, if we can observe repeated states, that solution can be further optimized by applying memoization. The memoization-based solution can be converted to a dynamic programming approach.

Write some applications of Dynamic Programming.

DP finds applications in optimization, combinatorial, graph algorithms, and string problems.

What is dynamic programming, and where is it used?

Dynamic programming is an optimization method used in various programming problems. It is used in problems where the solution depends on smaller overlapping subproblems. We use it to memorize the results so that they can easily be used later when needed.

What are overlapping subproblems?

A problem has overlapping subproblems if it can be divided into more minor problems that are reused multiple times.

What is the optimal substructure?

If an optimal solution can be created from the optimal solutions of its subproblems, a problem is said to have an optimal substructure.

Conclusion

This article discusses the problem of counting the total numbers in the range [L, R] whose sum of digits is Y. In detail, we have covered three different approaches to solving the problem and saw the implementation of all three approaches in C++ and Java. We also discussed the time complexity and space complexity of each approach. We suggest you solve them to gain more confidence in these problems. These questions are asked during various coding contests as well as placement tests and thus are very important.

We hope this blog has helped you enhance your knowledge of the Stock problem and Dynamic Programming. If you want to enhance more, then check out our blogs.

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundles for placement preparations.

However, you may consider our paid courses to give your career an edge over others!