Count numbers (smaller than or equal to N) with given digit sum
Given a number N and a sum S, find the count of numbers upto N that have digit sum equal to S.
Examples: Input : N = 100, S = 4 Output : 5 Upto 100 only 5 numbers(4, 13, 22, 31, 40) can produce 4 as their sum of digits. Input : N = 1000, S = 1 Output : 4 Upto 1000 only 4 numbers(1, 10, 100 and 1000) can produce 1 as their sum of digits.
We can do a digit DP having state (current index, whether the currently constructed number of i digits is equal or less than the number formed by first i digits of N, the sum of digits of currently constructed number). Let dp[i][tight][sum_so_far] denotes the count of numbers whose first i digits have been considered and tight denotes whether the currently constructed number is equal or less than number formed by first i digits of N. If tight is true, then it means that currently constructed number is equal to the number constructed by first i digits of N. If it is false then it means that currently constructed number is less than the number constructed by first i digits of N. sum_so_far denotes the sum of digits of currently constructed number. Base Case: If i = number of digits in N, sum_so_far = Sum, then answer = 1 else answer is 0. Transitions: For filling (i+1)th digit we can consider following – If tight is true, then it means that our constructed number is still equal to number formed by first i digits of N. We can try our current possible digit value from 0 to (i+1)th digit of N. If we try the digit more than (i+1)th digit, then the constructed number will become greater than number formed by first i digits of N, which will violate the property that our constructed number should be <= N. If tight is false, then it means that number constructed from first i – 1 digits has become less than number constructed from the first i – 1 digit of N, So it means that our number can never exceed N, so we can choose the any digit from 0 to 9. nsum_so_far can be obtained by adding sum_so_far and current digit(currdigit). Finally we will return answer which is count of numbers upto N that have digit sum equal to S.
C++
#include <bits/stdc++.h>using namespace std;// N can be max 10^18 and hence digitsum will be 162 maximum.long long dp[18][2][162];long long solve(int i, bool tight, int sum_so_far, int Sum, string number, int len){ if (i == len) { // If sum_so_far equals to given sum then // return 1 else 0 if (sum_so_far == Sum) return 1; else return 0; } long long& ans = dp[i][tight][sum_so_far]; if (ans != -1) { return ans; } ans = 0; bool ntight; int nsum_so_far; for (char currdigit = '0'; currdigit <= '9'; currdigit++) { // Our constructed number should not become // greater than N. if (!tight && currdigit > number[i]) { break; } // If tight is true then it will also be true for (i+1) digit. ntight = tight || currdigit < number[i]; nsum_so_far = sum_so_far + (currdigit - '0'); ans += solve(i + 1, ntight, nsum_so_far, Sum, number, len); } return ans;}// Driver codeint main(){ long long count = 0; long long sum = 4; string number = "100"; memset(dp, -1, sizeof dp); cout << solve(0, 0, 0, sum, number, number.size()); return 0;} |
Java
// Java program to count 2s from 0 to n import java.io.*;class GFG {// N can be max 10^18 and hence // digitsum will be 162 maximum. static long dp[][][] = new long[18][2][162]; static long solve(int i, boolean tight, int sum_so_far, int Sum, String number, int len) { if (i == len) { // If sum_so_far equals to given sum then // return 1 else 0 if (sum_so_far == Sum) return 1; else return 0; } long ans = dp[i][1][sum_so_far]; if (ans != -1) { return ans; } ans = 0; boolean ntight; int nsum_so_far; for (char currdigit = '0'; currdigit <= '9'; currdigit++) { // Our constructed number should not become // greater than N. if (!tight && currdigit > number.charAt(i)) { break; } // If tight is true then it will // also be true for (i+1) digit. ntight = tight || currdigit < number.charAt(i); nsum_so_far = sum_so_far + (currdigit - '0'); ans += solve(i + 1, ntight, nsum_so_far, Sum, number, len); } return ans; } // Driver code public static void main(String[] args) { long count = 0; int sum = 4; String number = "100"; for(int i = 0; i < 18; i++) { for(int j = 0; j < 2; j++) { for(int k = 0; k < 162; k++) dp[i][j][k] = -1; } } System.out.println( solve(0, false, 0, sum, number, number.length())); }} // This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the given approach. def solve(i, tight, sum_so_far, Sum, number, length): if i == length: # If sum_so_far equals to given # sum then return 1 else 0 if sum_so_far == Sum: return 1 else: return 0 ans = dp[i][tight][sum_so_far] if ans != -1: return ans ans = 0 for currdigit in range(0, 10): currdigitstr = str(currdigit) # Our constructed number should # not become greater than N. if not tight and currdigitstr > number[i]: break # If tight is true then it will also be true for (i+1) digit. ntight = tight or currdigitstr < number[i] nsum_so_far = sum_so_far + currdigit ans += solve(i + 1, ntight, nsum_so_far, Sum, number, length) return ans # Driver code if __name__ == "__main__": count, Sum = 0, 4 number = "100" dp = [[[-1 for i in range(162)] for j in range(2)] for k in range(18)] print(solve(0, 0, 0, Sum, number, len(number)))# This code is contributed by Rituraj Jain |
C#
// C# program to count 2s from 0 to n using System;class GFG { // N can be max 10^18 and hence // digitsum will be 162 maximum. static long [ , , ]dp = new long[18,2,162]; static long solve(int i, bool tight, int sum_so_far, int Sum, String number, int len) { if (i == len) { // If sum_so_far equals to given sum then // return 1 else 0 if (sum_so_far == Sum) return 1; else return 0; } long ans = dp[i,1,sum_so_far]; if (ans != -1) { return ans; } ans = 0; bool ntight; int nsum_so_far; for (char currdigit = '0'; currdigit <= '9'; currdigit++) { // Our constructed number should not become // greater than N. if (!tight && currdigit > number[i]) { break; } // If tight is true then it will // also be true for (i+1) digit. ntight = tight || currdigit < number[i]; nsum_so_far = sum_so_far + (currdigit - '0'); ans += solve(i + 1, ntight, nsum_so_far, Sum, number, len); } return ans; } // Driver code public static void Main(String[] args) { int sum = 4; String number = "100"; for(int i = 0; i < 18; i++) { for(int j = 0; j < 2; j++) { for(int k = 0; k < 162; k++) dp[i,j,k] = -1; } } Console.WriteLine( solve(0, false, 0, sum, number, number.Length)); } } // This code has been contributed by Rajput-Ji |
Javascript
// Javascript code for the above approach// N can be max 10^18 and hence // digitsum will be 162 maximum. let dp = new Array(18);for (let i = 0; i < dp.length; i++) { dp[i] = new Array(2); for (let j = 0; j < 2; j++) { dp[i][j] = new Array(162).fill(-1); }}function solve(i, tight, sum_so_far, Sum, number, len) { if (i === len) { // If sum_so_far equals to given sum then // return 1 else 0 if (sum_so_far === Sum) return 1; else return 0; } if (dp[i][1][sum_so_far] !== -1) { return dp[i][1][sum_so_far]; } let ans = 0; let ntight; let nsum_so_far; for (let currdigit = '0'; currdigit <= '9'; currdigit++) { // Our constructed number should not become // greater than N. if (!tight && currdigit > number.charAt(i)) { break; } // If tight is true then it will // also be true for (i+1) digit. ntight = tight || currdigit < number.charAt(i); nsum_so_far = sum_so_far + (currdigit - '0'); ans += solve(i + 1, ntight, nsum_so_far, Sum, number, len); } return ans;}// Driver code let count = 0;let sum = 4;let number = "100";console.log(solve(0, false, 0, sum, number, number.length))// This code is contributed by lokeshpotta20. |
5
Time Complexity: 2(tight) * Sum * log 10(N) * 10(transitions) = 20*log 10(N)*Sum.
Auxiliary Space: O(log N * 2 * 162).
Here log N is for the number of digits in the given number N, 2 is for the boolean tight value and 162 is for the maximum sum of digits as N can be of 10^18.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
