Count of numbers from range [L, R] whose sum of digits is Y | Set 2

0 0 15 minutes read

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

Examples:

Input: L = 500, R = 1000, Y = 6
Output: 3
Explanation:
Numbers in the range [500, 600] whose sum of digits is Y(= 6) are:
501 = 5 + 0 + 1 = 6
510 = 5 + 1 + 0 = 6
600 = 6 + 0 + 0 = 6
Therefore, the required output is 3.

Input: L = 20, R = 10000, Y = 14
Output: 540

Naive Approach: Refer to previous post to solve this problem by iterating over all the numbers in the range [L, R], and for every number, check if its sum of digits is equal to Y or not. If found to be true, then increment the count. Finally, print the count obtained.

Time Complexity: O(R – L + 1) * log₁₀(R)
Auxiliary Space: O(1)

Efficient approach: To optimize the above approach, the idea is to use Digit DP using the following recurrence relation:

$cntNum(i, sum, tight) = \sum^{9}_{i=0} cntNum(i + 1, (sum - i), tight & (i == end)$

where, sum: Represents sum of digits.
tight: Check if sum of digits exceed Y or not.
end: Stores the maximum possible value of i^th digit of a number.
cntNum(N, Y, tight): Returns the count of numbers in the range [0, X] whose sum of digits is Y.

Before moving into the DP solution, it is good practice to write down the recursive code.

Here is the recursive code –

C++

// C++ Program for the same approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the sum of digits
// of numbers in the range [0, X]
int cntNum(string X, int i, int sum, int tight)
{
   
    // Check if count of digits in a number
    // greater than count of digits in X
    if (i >= X.length() || sum < 0) {
 
        // Check if sum of digits of a
        // number is equal to Y
        if (sum == 0) {
            return 1;
        }
 
        return 0;
    }
 
    // Stores count of numbers whose
    // sum of digits is Y
    int res = 0;
 
    // Check if the number
    // exceeds Y or not
    int end = tight != 0 ? X[i] - '0' : 9;
 
    // Iterate over all possible
    // values of i-th digits
    for (int j = 0; j <= end; j++) {
 
        // Update res
        res += cntNum(X, i + 1, sum - j,
                    (tight > 0 & (j == end)) ==
                            true ? 1 : 0);
    }
 
    // Return res
    return res;
}
// Utility function to count the numbers in
// the range [L, R] whose sum of digits is Y
static int UtilCntNumRange(int L,int R,int Y)
{
 
    // Base Case
    if (R == 0 && Y == 0) {
 
        return 1;
    }
// Stores numbers in the form
    // of its equivalent String
    string str = to_string(R);
     
    // Stores count of numbers
    // in the range [0, R]
    int cntR = cntNum(str, 0, Y,
                    1);
 
    // Update str
    str = to_string(L - 1);
    // Stores count of numbers in
    // the range [0, L - 1]
    int cntL = cntNum(str, 0, Y,
                    1);
 
    return (cntR - cntL);
}
 
// Driver code
int main()
{
    int L = 20, R = 10000, Y = 14;
    cout<<(UtilCntNumRange(L, R, Y));
}
 
// This code is contributed by shinjanpatra

Java

// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find the sum of digits
// of numbers in the range [0, X]
static int cntNum(String X, int i, int sum,
           int tight)
 {
    // Check if count of digits in a number
    // greater than count of digits in X
    if (i >= X.length() || sum < 0) {
  
        // Check if sum of digits of a
        // number is equal to Y
        if (sum == 0) {
            return 1;
        }
  
        return 0;
    }
  
    // Stores count of numbers whose
    // sum of digits is Y
    int res = 0;
  
    // Check if the number
    // exceeds Y or not
    int end = tight != 0 ? X.charAt(i) - '0' : 9;
  
    // Iterate over all possible
    // values of i-th digits
    for (int j = 0; j <= end; j++) {
  
        // Update res
        res += cntNum(X, i + 1, sum - j,
                      (tight > 0 & (j == end)) ==
                               true ? 1 : 0);
    }
  
    // Return res
    return res;
 }
// Utility function to count the numbers in
// the range [L, R] whose sum of digits is Y
static int UtilCntNumRange(int L,int R,int Y)
 {
  
     // Base Case
    if (R == 0 && Y == 0) {
  
        return 1;
    }
   // Stores numbers in the form
    // of its equivalent String
    String str = String.valueOf(R);
     
     // Stores count of numbers
    // in the range [0, R]
    int cntR = cntNum(str, 0, Y,
                      1);
  
    // Update str
    str = String.valueOf(L - 1);
    // Stores count of numbers in
    // the range [0, L - 1]
    int cntL = cntNum(str, 0, Y,
                      1);
  
    return (cntR - cntL);
 }
// Driver Code
 public static void main (String[] args)
    {
      int L = 20, R = 10000, Y = 14;
      System.out.print(UtilCntNumRange(L, R, Y));
    }
}
// This code is contributed by Debojyoti Mandal

Python3

# Python program for the above approach
# Function to find the sum of digits
# of numbers in the range [0, X]
def cntNum(X, i, sum, tight):
 
    # Check if count of digits in a number
    # greater than count of digits in X
    if (i >= len(X) or sum < 0):
  
        # Check if sum of digits of a
        # number is equal to Y
        if (sum == 0):
            return 1
     
        return 0
  
    # Stores count of numbers whose
    # sum of digits is Y
    res = 0
  
    # Check if the number
    # exceeds Y or not
    end = ord(X[i]) - ord('0') if tight else 9
  
    # Iterate over all possible
    # values of i-th digits
    for j in range(end+1):
  
        # Update res
        res += cntNum(X, i + 1, sum - j,1 if((tight > 0 and (j == end)) == True) else 0)
  
    # Return res
    return res
 
# Utility function to count the numbers in
# the range [L, R] whose sum of digits is Y
def UtilCntNumRange(L, R, Y):
 
     # Base Case
    if (R == 0 and Y == 0):
  
        return 1
 
    # Stores numbers in the form
    # of its equivalent String
    Str = str(R)
 
     # Stores count of numbers
    # in the range [0, R]
    cntR = cntNum(Str, 0, Y,1)
  
    # Update str
    Str = str(L - 1)
     
    # Stores count of numbers in
    # the range [0, L - 1]
    cntL = cntNum(Str, 0, Y, 1)
  
    return (cntR - cntL)
 
# Driver Code
 
L, R, Y = 20, 10000, 14
print(UtilCntNumRange(L, R, Y))
 
# This code is contributed by shinjanpatra

C#

// C# program for the above approach
using System;
class GFG
{
   
    // Function to find the sum of digits
    // of numbers in the range [0, X]
    static int cntNum(string X, int i, int sum, int tight)
    {
       
        // Check if count of digits in a number
        // greater than count of digits in X
        if (i >= X.Length || sum < 0) {
 
            // Check if sum of digits of a
            // number is equal to Y
            if (sum == 0) {
                return 1;
            }
 
            return 0;
        }
 
        // Stores count of numbers whose
        // sum of digits is Y
        int res = 0;
 
        // Check if the number
        // exceeds Y or not
        int end = tight != 0 ? X[i] - '0' : 9;
 
        // Iterate over all possible
        // values of i-th digits
        for (int j = 0; j <= end; j++) {
 
            // Update res
            res += cntNum(
                X, i + 1, sum - j,
                (tight > 0 & (j == end)) == true ? 1 : 0);
        }
 
        // Return res
        return res;
    }
    // Utility function to count the numbers in
    // the range [L, R] whose sum of digits is Y
    static int UtilCntNumRange(int L, int R, int Y)
    {
        // Base Case
        if (R == 0 && Y == 0) {
 
            return 1;
        }
        // Stores numbers in the form
        // of its equivalent String
        string str = R.ToString();
 
        // Stores count of numbers
        // in the range [0, R]
        int cntR = cntNum(str, 0, Y, 1);
 
        // Update str
        str = (L - 1).ToString();
        // Stores count of numbers in
        // the range [0, L - 1]
        int cntL = cntNum(str, 0, Y, 1);
 
        return (cntR - cntL);
    }
   
    // Driver Code
    public static void Main(string[] args)
    {
        int L = 20, R = 10000, Y = 14;
        Console.WriteLine(UtilCntNumRange(L, R, Y));
    }
}
 
// This code is contributed by ukasp.

Javascript

// JavaScript program for the above approach
// Function to find the sum of digits
// of numbers in the range [0, X]
function cntNum( X, i, sum, tight)
 {
    // Check if count of digits in a number
    // greater than count of digits in X
    if (i >= X.length || sum < 0) {
  
        // Check if sum of digits of a
        // number is equal to Y
        if (sum == 0) {
            return 1;
        }
  
        return 0;
    }
  
    // Stores count of numbers whose
    // sum of digits is Y
    var res = 0;
  
    // Check if the number
    // exceeds Y or not
    var end = tight != 0 ? X[i].charCodeAt(0) - '0'.charCodeAt(0) : 9;
  
    // Iterate over all possible
    // values of i-th digits
    for (var j = 0; j <= end; j++) {
  
        // Update res
        res += cntNum(X, i + 1, sum - j,
                      (tight > 0 & (j == end)) ==
                               true ? 1 : 0);
    }
  
    // Return res
    return res;
 }
// Utility function to count the numbers in
// the range [L, R] whose sum of digits is Y
function UtilCntNumRange(L, R, Y)
 {
     // Base Case
    if (R == 0 && Y == 0) {
  
        return 1;
    }
   // Stores numbers in the form
    // of its equivalent String
    var str = (R).toString();
     
     // Stores count of numbers
    // in the range [0, R]
    var cntR = cntNum(str, 0, Y,
                      1);
  
    // Update str
     str = (L - 1).toString();
    // Stores count of numbers in
    // the range [0, L - 1]
    var cntL = cntNum(str, 0, Y,
                      1);
  
    return (cntR - cntL);
 }
// Driver Code
 
      var L = 20, R = 10000, Y = 14;
      document.write(UtilCntNumRange(L, R, Y));
     
 
// This code is contributed by shivanisinghss2110

Output

Follow the steps below to solve the problem using DP.

Initialize a 3D array dp[N][Y][tight] to compute and store the values of all subproblems of the above recurrence relation.
Finally, return the value of dp[N][sum][tight].

Below is the implementation of the above approach:

C++

// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
#define M 1000
 
// Function to find the sum of digits
// of numbers in the range [0, X]
int cntNum(string X, int i, int sum,
           int tight, int dp[M][M][2])
{
    // Check if count of digits in a number
    // greater than count of digits in X
    if (i >= X.length() || 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 res = 0;
 
    // Check if the number
    // exceeds Y or not
    int end = tight ? X[i] - '0' : 9;
 
    // Iterate over all possible
    // values of i-th digits
    for (int j = 0; j <= end; j++) {
 
        // Update res
        res += cntNum(X, i + 1, sum - j,
                      (tight & (j == end)), dp);
    }
 
    // Return res
    return dp[sum][i][tight]=res;
}
 
// Utility function to count the numbers in
// the range [L, R] whose sum of digits is Y
int UtilCntNumRange(int L, int R, int Y)
{
    // Base Case
    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[M][M][2];
 
    // Initialize dp[][][]
    memset(dp, -1, sizeof(dp));
 
    // Stores count of numbers
    // in the range [0, R]
    int cntR = cntNum(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 cntL = cntNum(str, 0, Y,
                      true, dp);
 
    return (cntR - cntL);
}
 
// Driver Code
int main()
{
    int L = 20, R = 10000, Y = 14;
    cout << UtilCntNumRange(L, R, Y);
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
static final int M = 1000;
 
// Function to find the sum of digits
// of numbers in the range [0, X]
static int cntNum(String X, int i, int sum,
           int tight, int dp[][][])
{
    // Check if count of digits in a number
    // greater than count of digits in X
    if (i >= X.length() || sum < 0) {
 
        // Check 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 res = 0;
 
    // Check if the number
    // exceeds Y or not
    int end = tight != 0 ? X.charAt(i) - '0' : 9;
 
    // Iterate over all possible
    // values of i-th digits
    for (int j = 0; j <= end; j++) {
 
        // Update res
        res += cntNum(X, i + 1, sum - j,
                      (tight > 0 & (j == end)) == 
                               true ? 1 : 0, dp);
    }
 
    // Return res
    return dp[sum][i][tight]=res;
}
 
// Utility function to count the numbers in
// the range [L, R] whose sum of digits is Y
static int UtilCntNumRange(int L, int R, int Y)
{
    // Base Case
    if (R == 0 && Y == 0) {
 
        return 1;
    }
 
    // Stores numbers in the form
    // of its equivalent String
    String str = String.valueOf(R);
 
    // Stores overlapping subproblems
    int [][][]dp = new int[M][M][2];
 
    // Initialize dp[][][]
    for(int i = 0; i < M; i++)
    {
        for (int j = 0; j < M; j++) {
            for (int k = 0; k < 2; k++)
                dp[i][j][k] = -1;
        }
    }
 
    // Stores count of numbers
    // in the range [0, R]
    int cntR = cntNum(str, 0, Y,
                      1, dp);
 
    // Update str
    str = String.valueOf(L - 1);
 
    // Initialize dp[][][]
    for(int i = 0; i < M; i++)
    {
        for (int j = 0; j < M; j++) {
            for (int k = 0; k < 2; k++)
                dp[i][j][k] = -1;
        }
    }
 
    // Stores count of numbers in
    // the range [0, L - 1]
    int cntL = cntNum(str, 0, Y,
                      1, dp);
 
    return (cntR - cntL);
}
 
// Driver Code
public static void main(String[] args)
{
    int L = 20, R = 10000, Y = 14;
    System.out.print(UtilCntNumRange(L, R, Y));
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python program for the above approach
M = 1000
 
# Function to find the sum of digits
# of numbers in the range [0, X]
def cntNum(X, i, sum, tight, dp):
   
    # Check if count of digits in a number
    # greater than count of digits in X
    if (i >= len(X) or sum < 0):
 
        # Check 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
    res, end = 0, 9
 
    # Check if the number
    # exceeds Y or not
    if tight:
        end = ord(X[i]) - ord('0')
    # end = tight ? X[i] - '0' : 9;
 
    # Iterate over all possible
    # values of i-th digits
    for j in range(end + 1):
 
        # Update res
        res += cntNum(X, i + 1, sum - j,
                      (tight & (j == end)), dp)
 
    # Return res
    dp[sum][i][tight] = res
    return res
 
# Utility function to count the numbers in
# the range [L, R] whose sum of digits is Y
def UtilCntNumRange(L, R, Y):
   
    # Base Case
    if (R == 0 and Y == 0):
 
        return 1
 
    # Stores numbers in the form
    # of its equivalent
    strr = str(R)
 
    # Stores overlapping subproblems
    dp = [[[-1 for i in range(2)] for i in range(M)] 
                                  for i in range(M)]
 
    # Initialize dp[][][]
    # memset(dp, -1, sizeof(dp))
 
    # Stores count of numbers
    # in the range [0, R]
    cntR = cntNum(strr, 0, Y, True, dp)
 
    # Update str
    strr = str(L - 1)
 
    # Initialize dp[][][]
    # memset(dp, -1, sizeof(dp))
 
    # Stores count of numbers in
    # the range [0, L - 1]
    cntL = cntNum(strr, 0, Y, True, dp)
 
    return (cntR - cntL)
 
# Driver Code
if __name__ == '__main__':
    L, R, Y = 20, 10000, 14
    print(UtilCntNumRange(L, R, Y))
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
 
class GFG{
 
static readonly int M = 1000;
 
// Function to find the sum of digits
// of numbers in the range [0, X]
static int cntNum(String X, int i, int sum,
                 int tight, int [,,]dp)
{
     
    // Check if count of digits in a number
    // greater than count of digits in X
    if (i >= X.Length || sum < 0) 
    {
         
        // Check 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 res = 0;
 
    // Check if the number
    // exceeds Y or not
    int end = tight != 0 ? X[i] - '0' : 9;
 
    // Iterate over all possible
    // values of i-th digits
    for(int j = 0; j <= end; j++) 
    {
         
        // Update res
        res += cntNum(X, i + 1, sum - j,
                    (tight > 0 & (j == end)) ==
                      true ? 1 : 0, dp);
    }
 
    // Return res
    return dp[sum][i][tight] = res;
}
 
// Utility function to count the numbers in
// the range [L, R] whose sum of digits is Y
static int UtilCntNumRange(int L, int R, int Y)
{
     
    // Base Case
    if (R == 0 && Y == 0) 
    {
        return 1;
    }
 
    // Stores numbers in the form
    // of its equivalent String
    String str = String.Join("", R);
     
    // Stores overlapping subproblems
    int [,,]dp = new int[M, M, 2];
 
    // Initialize [,]dp[]
    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < M; j++)
        {
            for(int k = 0; k < 2; k++)
                dp[i, j, k] = -1;
        }
    }
 
    // Stores count of numbers
    // in the range [0, R]
    int cntR = cntNum(str, 0, Y,
                      1, dp);
 
    // Update str
    str = String.Join("",L - 1);
 
    // Initialize [,]dp[]
    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < M; j++)
        {
            for(int k = 0; k < 2; k++)
                dp[i, j, k] = -1;
        }
    }
 
    // Stores count of numbers in
    // the range [0, L - 1]
    int cntL = cntNum(str, 0, Y,
                      1, dp);
 
    return (cntR - cntL);
}
 
// Driver Code
public static void Main(String[] args)
{
    int L = 20, R = 10000, Y = 14;
     
    Console.Write(UtilCntNumRange(L, R, Y));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript program for the above approach
let M = 1000;
 
// Function to find the sum of digits
// of numbers in the range [0, X]
function cntNum(X, i, sum, tight, dp)
{
 
    // Check if count of digits in a number
    // greater than count of digits in X
    if (i >= X.length || sum < 0) {
  
        // Check 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
    let res = 0;
  
    // Check if the number
    // exceeds Y or not
    let end = tight != 0 ? X[i].charCodeAt(0) - '0'.charCodeAt(0) : 9;
  
    // Iterate over all possible
    // values of i-th digits
    for (let j = 0; j <= end; j++) {
  
        // Update res
        res += cntNum(X, i + 1, sum - j,
                      (tight > 0 & (j == end)) ==
                               true ? 1 : 0, dp);
    }
  
    // Return res
    return dp[sum][i][tight]=res;
}
 
// Utility function to count the numbers in
// the range [L, R] whose sum of digits is Y
function UtilCntNumRange(L,R,Y)
{
    // Base Case
    if (R == 0 && Y == 0) {
  
        return 1;
    }
  
    // Stores numbers in the form
    // of its equivalent String
    let str = (R).toString();
  
    // Stores overlapping subproblems
    let dp = new Array(M);
  
    // Initialize dp[][][]
    for(let i = 0; i < M; i++)
    {
        dp[i]=new Array(M);
        for (let j = 0; j < M; j++) {
            dp[i][j]=new Array(2);
            for (let k = 0; k < 2; k++)
                dp[i][j][k] = -1;
        }
    }
  
    // Stores count of numbers
    // in the range [0, R]
    let cntR = cntNum(str, 0, Y,
                      1, dp);
  
    // Update str
    str = (L - 1).toString();
  
    // Initialize dp[][][]
    for(let i = 0; i < M; i++)
    {
        for (let j = 0; j < M; j++) {
            for (let k = 0; k < 2; k++)
                dp[i][j][k] = -1;
        }
    }
  
    // Stores count of numbers in
    // the range [0, L - 1]
    let cntL = cntNum(str, 0, Y,
                      1, dp);
  
    return (cntR - cntL);
}
 
// Driver Code
let L = 20, R = 10000, Y = 14;
document.write(UtilCntNumRange(L, R, Y));
 
// This code is contributed by patel2127
</script>

Output

Time Complexity: O(Y * log₁₀(R) * 10)
Auxiliary Space: O(Y * log₁₀(R)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!