Count of Numbers in the range [L, R] Whose Sum Of Digits is Y

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

1. Call the corresponding ‘count_numbers()’ function to count the numbers in the range [L, R] whose sum of digits is Y.
    
2. Initialize a variable ‘total’ for storing the count of the numbers.
    
3. 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.
   
   1. For each number, find the sum of all its digits.
       
   2. 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).
       
   3. 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₁₀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₁₀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₁₀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

1. 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).
    
2. If the sum equals zero, the current sum is equal to Y, so simply return value one here.
    
3. 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.
    
4. Now, from here, two cases arise:
   1. 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.
       
   2. 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
       
5. 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

1. 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).
    
2. If the ‘count_numbers()’ function is calculated for constraints idx, sum, and tight then simply return the value from the dp array.
    
3. If the sum equals zero, the current sum is equal to Y, so simply return value one here.
    
4. 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.
    
5. Now, from here, two cases arise:
   1. 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.’
       
   2. 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’.
       
6. Store the result in the corresponding dp array and return the variable ‘ans’ as the total count of numbers less than string ‘s’.
    
7. 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₁₀(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₁₀(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₁₀(R) * 10).

Space Complexity

O(Y * log₁₀(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₁₀R * 2).

Check out Longest Common Substring

Frequently Asked Questions

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.

• Introduction to Digit DP
• Introduction to digit DP
• Longest Increasing Subsequence Size
   

And many more on our platform Coding Ninjas Studio.

Refer to our Guided Path to upskill yourself in DSA, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

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!

Happy Learning, Ninjas!