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. |
Output:
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.
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!
