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) * log10(R)
Auxiliary Space: O(1)
Efficient approach: To optimize the above approach, the idea is to use Digit DP using the following recurrence relation:
where, sum: Represents sum of digits.
tight: Check if sum of digits exceed Y or not.
end: Stores the maximum possible value of ith 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 Ystatic 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 codeint 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 approachimport 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 Ystatic 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 Ydef 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 CodeL, R, Y = 20, 10000, 14print(UtilCntNumRange(L, R, Y))# This code is contributed by shinjanpatra |
C#
// C# program for the above approachusing 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 Yfunction 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
540
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 Yint 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 Codeint main(){ int L = 20, R = 10000, Y = 14; cout << UtilCntNumRange(L, R, Y);} |
Java
// Java program for the above approachimport 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 Ystatic 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 Codepublic 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 approachM = 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 Ydef 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 Codeif __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 approachusing 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 Ystatic 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 Codepublic 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 approachlet 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 Yfunction 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 Codelet L = 20, R = 10000, Y = 14;document.write(UtilCntNumRange(L, R, Y));// This code is contributed by patel2127</script> |
Output
540
Time Complexity: O(Y * log10(R) * 10)
Auxiliary Space: O(Y * log10(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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
