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 code int 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 neveropen!