Pre-requisites: Recursion, Dynamic Programming, Digit DP
Given an integer Y and a range [L, R], the task is to find the count of all numbers from the given range whose sum of digits is equal to Y.
Examples:
Input: L = 0, R = 11, Y = 2
Output: 2
2 -> 2
11 -> 1 + 1 = 2
Input: L = 500, R = 1000, Y = 6
Output: 3
Constraints:
0 <= L <= R <= 10^18
0 <= Y <= 162 (Which is the maximum possible sum a 18 digit number can have)
Approach: Firstly generalizing the question, [L, R] can be written as [0, R] – [0, L-1], i.e. first finding all the numbers in the range[0, R] whose digit sum = Y, and then for the range[0, L-1], then finally subtracting each values to get out desired result. So for the case of digit let’s store the digits of number L and R in 2 separate vectors so that accessing its digit would be easier. Then we need a function that will carry (current_index, flag, sum). This function is the main part of our logic. Initializing current_index = 0, flag = 0, sum = 0.
Let’s say R = 462, this number has 3 indexes i.e. 0, 1, 2. Now check in how many ways can you fill the 0th index. On observation we can say we can fill 0th index as 0, 1, 2, 3 and 4. If we exceed 4, then we would form a number greater than 462.
Now, if you have inserted 0 in 0th index then what can be the possibility for 1st index ? Answer – 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Since you have a number 0 in the 0th index you can fill any number from 0-9 in the 1st index. Okay as you can fill any number in next index, you will turn flag = 1. flag = 1 tell us that we have the advantage to fill anything from 0-9. Similarly thinking up for the other indexes.
Now if we see the base condition
if(current_index == n) { if(sum == Y) return 1; else return 0;}
Below is the implementation of the above approach:
C++
#include<bits/stdc++.h>using namespace std;// function to convert digit to vectorvector<int> digitToVec(int n) { vector<int> a; while (n) { a.push_back(n % 10); n = n / 10; } reverse(a.begin(), a.end()); return a;}int Y; // setting Y as globalint dp[19][2][18 * 9 + 1]; // 3D dpint func(int ind, int flag, int sum, vector<int> a) { if (ind == a.size()) { if (sum == Y) return 1; else return 0; } if (dp[ind][flag][sum] != -1) return dp[ind][flag][sum]; // if flag = 0, I know I can only fill from 0 to a[ind] // if flag = 1, I have the advantage to fill from 0 to 9 int limit = 9; if (flag == 0) limit = a[ind]; int cnt = 0; for (int num = 0; num <= limit; num++) { // if flag = 0, which means no advantage // and I am still filling the same number as a[ind] means giving him no advantage // hence the next recursion call flag still stays as 0 if (flag == 0 && num == a[ind]) { cnt += func(ind + 1, 0, sum + num, a); } else { cnt += func(ind + 1, 1, sum + num, a); } } return dp[ind][flag][sum] = cnt;}// intermediate function helping to initialize all values of func()int ans(int n) { vector<int> a = digitToVec(n); memset(dp, -1, sizeof dp); // initializing dp as -1 return func(0, 0, 0, a);}// Driver codeint main() { int l, r; cin >> l >> r >> Y; cout << ans(r) - ans(l - 1); return 0;} |
Java
// Java program to implement the approachimport java.util.*;class GFG{ // function to convert digit to vector static ArrayList<Integer> digitToVec(int n) { ArrayList<Integer> a = new ArrayList<Integer>(); while (n > 0) { a.add(n % 10); n = n / 10; } Collections.reverse(a); return a; } static int Y; // setting Y as global static int[][][] dp = new int[19][2][18 * 9 + 1]; // 3D dp static int func(int ind, int flag, int sum, ArrayList<Integer> a) { if (ind == a.size()) { if (sum == Y) return 1; else return 0; } if (dp[ind][flag][sum] != -1) return dp[ind][flag][sum]; // if flag = 0, I know I can only fill from 0 to // a[ind] // if flag = 1, I have the advantage to fill from 0 // to 9 int limit = 9; if (flag == 0) limit = a.get(ind); int cnt = 0; for (int num = 0; num <= limit; num++) { // if flag = 0, which means no advantage // and I am still filling the same number as // a[ind] means giving him no advantage hence // the next recursion call flag still stays as 0 if (flag == 0 && num == a.get(ind)) { cnt += func(ind + 1, 0, sum + num, a); } else { cnt += func(ind + 1, 1, sum + num, a); } } return dp[ind][flag][sum] = cnt; } // intermediate function helping to initialize all // values of func() static int ans(int n) { ArrayList<Integer> a = digitToVec(n); for (int i = 0; i < 19; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 18 * 9 + 1; k++) dp[i][j][k] = -1; // initializing dp as -1 return func(0, 0, 0, a); } // Driver code public static void main(String[] args) { int l = 0; int r = 11; Y = 2; System.out.println(ans(r) - ans(l - 1)); }}// This code is contributed by phasing17 |
Python3
# Python3 implementation of the approachdp = [ [ [-1 for _ in range(18 * 9 + 1)] for __ in range(2)] for ___ in range(19)]# function to convert digit to vectordef digitToVec(n): a = []; while (n > 0) : a.append(n % 10); n = int(n / 10); a.reverse(); return a;Y = 2; # setting Y as globaldef func(ind, flag, sum, a): global Y if (ind == len(a)): if (sum == Y): return 1; else: return 0; if (dp[ind][flag][sum] != -1): return dp[ind][flag][sum]; # if flag = 0, I know I can only fill from 0 to a[ind] # if flag = 1, I have the advantage to fill from 0 to 9 limit = 9; if (flag == 0): limit = a[ind]; cnt = 0; for num in range(0, 1 + limit): # if flag = 0, which means no advantage # and I am still filling the same number as a[ind] means giving him no advantage # hence the next recursion call flag still stays as 0 if (flag == 0 and num == a[ind]) : cnt += func(ind + 1, 0, sum + num, a); else: cnt += func(ind + 1, 1, sum + num, a); dp[ind][flag][sum] = cnt; return dp[ind][flag][sum];# intermediate function helping to initialize all values of func()def ans(n) : a = digitToVec(n); return func(0, 0, 0, a);# Driver codel = 0r = 11;Y = 2;print(ans(r) - ans(l - 1));# This code is contributed by phasing17 |
C#
// C# program to implement the approachusing System;using System.Collections.Generic;class GFG { // function to convert digit to vector static List<int> digitToVec(int n) { List<int> a = new List<int>(); while (n > 0) { a.Add(n % 10); n = n / 10; } a.Reverse(); return a; } static int Y; // setting Y as global static int[, , ] dp = new int[19, 2, 18 * 9 + 1]; // 3D dp static int func(int ind, int flag, int sum, List<int> a) { if (ind == a.Count) { if (sum == Y) return 1; else return 0; } if (dp[ind, flag, sum] != -1) return dp[ind, flag, sum]; // if flag = 0, I know I can only fill from 0 to // a[ind] // if flag = 1, I have the advantage to fill from 0 // to 9 int limit = 9; if (flag == 0) limit = a[ind]; int cnt = 0; for (int num = 0; num <= limit; num++) { // if flag = 0, which means no advantage // and I am still filling the same number as // a[ind] means giving him no advantage hence // the next recursion call flag still stays as 0 if (flag == 0 && num == a[ind]) { cnt += func(ind + 1, 0, sum + num, a); } else { cnt += func(ind + 1, 1, sum + num, a); } } return dp[ind, flag, sum] = cnt; } // intermediate function helping to initialize all // values of func() static int ans(int n) { List<int> a = digitToVec(n); for (int i = 0; i < 19; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 18 * 9 + 1; k++) dp[i, j, k] = -1; // initializing dp as -1 return func(0, 0, 0, a); } // Driver code public static void Main(string[] args) { int l = 0; int r = 11; Y = 2; Console.WriteLine(ans(r) - ans(l - 1)); }}// This code is contributed by phasing17 |
Javascript
//JS implementation of the approachvar dp = new Array(19);for (var i = 0; i < 19; i++){ let l1 = new Array(18 * 9 + 1).fill(-1); dp[i] = [[...l1], [...l1]];} // 3D dp initialized to -1// function to convert digit to vectorfunction digitToVec(n) { let a = []; while (n > 0) { a.push(n % 10); n = Math.floor(n / 10); } a.reverse(); return a;}let Y; // setting Y as globalfunction func(ind, flag, sum, a) { if (ind == a.length) { if (sum == Y) return 1; else return 0; } if (dp[ind][flag][sum] != -1) return dp[ind][flag][sum]; // if flag = 0, I know I can only fill from 0 to a[ind] // if flag = 1, I have the advantage to fill from 0 to 9 let limit = 9; if (flag == 0) limit = a[ind]; let cnt = 0; for (let num = 0; num <= limit; num++) { // if flag = 0, which means no advantage // and I am still filling the same number as a[ind] means giving him no advantage // hence the next recursion call flag still stays as 0 if (flag == 0 && num == a[ind]) { cnt += func(ind + 1, 0, sum + num, a); } else { cnt += func(ind + 1, 1, sum + num, a); } } dp[ind][flag][sum] = cnt; return dp[ind][flag][sum];}// intermediate function helping to initialize all values of func()function ans(n) { let a = digitToVec(n); return func(0, 0, 0, a);}// Driver codelet l = 0, r = 11;Y = 2;console.log(ans(r) - ans(l - 1));// This code is contributed by phasing17 |
Output:
2
Now talking of the worst case Time Complexity: O(19 * 2 * (18 * 9) * 10)
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!
