Find the count of n-digit numbers whose sum of digits is equal to given sum s.
For example,
Input: n=2 and s=5 Output: 14, 23, 32, 41, 50 Explanation: we have to find those 2-digit numbers whose sum of digits is 5. Note that leading zeroes are not considered as digits, i.e. in above eg. we will not consider 05 as a 2-digit number.
Sum of n-digit numbers thought process
A brute force solution that first comes to mind is to consider each of the n-digits numbers, calculate the sum of digits of each number and count the ones where the sum of digits is s. But this solution is of exponential time complexity, we need to find a better solution. Let’s consider a few examples:
Numbers: numbers with n-digits and sum of digits s
Cnt(n,s): count of numbers
Input | Cnt(n,s) | Numbers |
n=2, sum=4 | 4 | 13, 22, 31, 40 |
n=2, sum=3 | 3 | 12, 21, 30 |
n=2, sum=2 | 2 | 11, 20 |
n=2, sum=1 | 1 | 10 |
n=2, sum=0 | 0 | – |
n=3, sum=5 | 15 | 104, 113, 122, 131, 140, 203, 212, 221, 230,302, 311, 320,401, 410,500 |
If we look closely at above example we can see that actual numbers in case of (n=3, sum=5) are generated from numbers in case of (n=2, sum=4), (n=2, sum=3), (n=2, sum=2), (n=2, sum=1) and (n=2, sum=0) by fixing the most significant digit. As stated in the question, leading zeroes cannot be considered as digits hence for the most significant digit available choices are ranging from 1 to 9 or given sum (whichever is less):
1 _ _ 2 _ _ 3 _ _ 4 _ _ 5 _ _
After fixing one digit we have got just 2 (n-1 i.e. 3-1 = 2) digits left with us and also the sum reduces by the digit value i, where i ranges from 1 to 9.
Let’s consider the case of (1 _ _), after fixing most significant digit to 1, problem reduces to remaining n – 1 = 3 – 1 = 2-digit numbers and reduced s = s – 1 = 5 – 1 = 4, which is nothing but the sub-problem cnt(n=2, s=4).
But also note that while fixing any digit other than the most significant digit, 0 can also be used as a digit, and the sub-problem is instead denoted by cntWithZero(n=2, s=4). The second digit can similarly be fixed but this time 0 is also a candidate:
1 0 _ 1 1 _ 1 2 _ 1 3 _ 1 4 _
After fixing 2 digits, the problem now reduces to 1-digit numbers and reduced sum (s-i) where i ranges from 0 to 9 or last reduced sum (whichever is less).
In this way for any n-digit number we can keep fixing a digit at a time and keep solving the sub-problems, until all n digits are fixed or in case s was small and it reaches zero before all digits were fixed.
As we had observed numbers for cnt(n=3, s=5) are generated by fixing the most significant digit, to find the solution for cnt(n=3, s=5) from its sub-problems –
1 _ _ => cntWithZero(2,4) => 5 (04, 13, 22, 31, 40)
2 _ _ => cntWithZero(2,3) => 4 (03, 12, 21, 30)
3 _ _ => cntWithZero(2,2) => 3 (02, 11, 20)
4 _ _ => cntWithZero(2,1) => 2 (01, 10)
5 _ _ => cntWithZero(2,0) => 1 (00)
Cnt(n=3, s=5) = cntWithZero(2,4) + cntWithZero(2,3) + cntWithZero(2,2) + cntWithZero(2,1) + cntWithZero(2,0) = 5 + 4 + 3 + 2 + 1 = 15
Considering this observation we can say that cnt(n, s) can be calculated using sub-problems such as cnt(n-1, s-i) where i ranges from 0 to s:
cnt(n, s) = SUM(cntWithZero(n-1, s-i)), where 1 <= i <= s cntWithZero() = SUM(cntWithZero(n-1, s-i)), where 0 <= i <= s
This shows this problem has optimal substructure (i.e. an optimal solution can be constructed from optimal solutions of subproblems), which is the first condition for application of dynamic programming.
long long int cntWithZero(int n, int sum) { if (n == 0) { if (sum == 0) return 1; return 0; } if (sum == 0) return 1; long long int ans = 0; for(int i=0; i<10; ++i) { if(sum – i >= 0) { ans += cntWithZero(n-1, sum-i); } } return ans; } long long int cnt(int n, int sum) { long long int ans = 0; for(int i=1; i<10; ++i) { if(sum – i >= 0) { ans += cntWithZero(n-1, sum-i); } } return ans; } int main(void) { int n=3, s=5; printf("%lld", cnt(n, s)); return 0; }
Recursive implementation Java
import java.io.*; class digit_sum { static int cntWithZero(int n, int sum) { if (n == 0) { if (sum == 0) return 1; return 0; } if (sum == 0) return 1; int ans = 0; for(int i=0; i<10; ++i) { if(sum - i >= 0) { ans += cntWithZero(n-1, sum-i); } } return ans; } static int cnt(int n, int sum) { int ans = 0; for(int i=1; i<10; ++i) { if(sum - i >= 0) { ans += cntWithZero(n-1, sum-i); } } return ans; } public static void main(String args[]) { int n=3, s=5; System.out.println(cnt(n, s)); } }
This implementation has exponential time complexity. Let’s have a look at the recursive function call tree to find the reason behind this:
In this example of cnt(n=3, s=5), subproblems such as cntWithZero(n=1, s=2) and cntWithZero(n=1, s=1) are calculated repeatedly. Our recursive algorithm for this problem solves the same subproblem over and over rather than always generating new subproblems. These are called overlapping subproblems, the second condition to apply dynamic programming.
As the two properties required for using Dynamic Programming: optimal substructure and overlapping subproblems hold, we can use DP for this problem. But before jumping to DP solution, there’s another way to resolve the issue of overlapping subproblems in a recursive approach: Memoized approach.
Memoised approach C++long long int memoized_table[101][101]; long long int cntWithZero(int n, int sum) { if (n == 0) { if (sum == 0) return 1; return 0; } if (memoized_table[n][ sum] == -1) { long long int ans = 0; for(int i=0; i<10; ++i) { if(sum – i >= 0) { ans += cntWithZero(n-1, sum -i); } memoized_table[n][ sum] = ans; } } return memoized_table[n][ sum]; } long long int cnt(int n, int sum) { long long int ans = 0; memset(memoized_table, -1, sizeof(memoized_table)); for(int i=1; i<10; ++i) { if(sum – i >= 0) { ans += cntWithZero(n-1, sum-i); } } return ans; } int main(void) { int n=3, s=5; printf("%lld", cnt(n, s)); return 0; }
Memoised approach Java
Java: import java.io.*; class digit_sum { static int memoized_table [][] = new int[101][101]; static int cntWithZero(int n, int sum) { if (n == 0) { if (sum == 0) return 1; return 0; } if (memoized_table[n][sum] == -1) { int ans = 0; for(int i=0; i<10; ++i) { if(sum - i >= 0) { ans += cntWithZero(n-1, sum -i); } memoized_table[n][ sum] = ans; } } return memoized_table[n][ sum]; } static int cnt(int n, int sum) { int ans = 0; for(int i = 0; i <= 100; ++i) { for(int j = 0; j <= 100; ++j) { memoized_table[i][j] = -1; } } for(int i=1; i<10; ++i) { if(sum - i >= 0) { ans += cntWithZero(n-1, sum -i); } } return ans; } public static void main(String[] args) { int n=3, s=5; System.out.println(cnt(n, s)); } }
The time complexity of the above implementation is O(ns) along with the space complexity of O(ns)
Sum of digits Dynamic Programming Approach
We go bottom-up in a dynamic programming approach. We will use a 2D array / DP table in the implementation. Start from the bottom i.e. i=0, j=0, and keep solving each sub-problem and store its result in DP table until we reach i=n and j=s.
Dynamic programming Java solution of sum of digits problem
import java.io.*; class digit_sum { static int cnt(int n, int sum) { int temp = 0; if(sum==0 || n==0) { return 0; } int dp [][] = new int[n+1][sum+1]; for(int i=0; i<=n; ++i) for(int j=0; j<=sum; ++j) dp[i][j] = 0; for(int i=0;i<=9 && i<=sum;i++) { dp[1][i]=1; } for(int i=2;i<n;i++) { for(int j=0;j<=sum;j++) { temp = 0; for(int k=0;k<=9;k++) { if(j-k>=0) { temp += dp[i-1][j-k]; } else break; } dp[i][j] = temp; } } temp=0; for(int k=1; n>1 && k<=9; k++) { if((sum-k)>=0) { temp += dp[n-1][sum-k]; } } dp[n][sum] = temp; return dp[n][sum]; } public static void main(String[] args) { int n=3, s=5; System.out.println(cnt(n, s)); } }
The time complexity of the dynamic programming solution is O(ns) with the space complexity of O(ns)
This article is contributed by Bhushan Aggrawal.