Introduction
Given two integers:
Find the number of n-digit positive integers whose digits add up to the given sum.
Important Rules
Example 1
Input
n = 2
sum = 2
Possible 2-digit numbers:
Output
2
Example 2
Input
n = 1
sum = 10
A single digit can only be between 0 and 9.
Output
-1
Example 3
Input
n = 2
sum = 10
Possible numbers:
19
28
37
46
55
64
73
82
91
Output
9
Brute Force Approach
A straightforward solution is:
Generate all possible n-digit numbers.
Calculate the digit sum of each number.
Count numbers whose digit sum equals the required sum.
Complexity
For 9-digit numbers:
10^9 possibilities
This is far too large to process within reasonable time limits.
We need a more efficient solution.
Dynamic Programming Approach
Instead of generating every number, we construct the answer digit by digit.
DP State
Let:
dp[i][j]
represent:
Number of i-digit numbers whose digit sum is j.
For example:
dp[2][5]
means:
Number of 2-digit numbers having digit sum 5.
Why Dynamic Programming Works
Suppose we already know:
dp[2][7]
Now we want:
dp[3][10]
The last digit can be:
0, 1, 2, ..., 9
Case 1: Last Digit = 3
Then the first two digits must contribute:
10 - 3 = 7
which is stored in:
dp[2][7]
Case 2: Last Digit = 5
Need:
dp[2][5]
Case 3: Last Digit = 8
Need:
dp[2][2]
Therefore:
dp[3][10]
=
dp[2][10]
+
dp[2][9]
+
dp[2][8]
+
...
+
dp[2][1]
This becomes our DP transition.
DP Formula
For every possible digit from 0 to 9:
dp[i][s]
=
Σ dp[i−1][s−digit]
or:
dp[i][s] += dp[i - 1][s - digit];
provided:
s >= digit
Initialization
The first digit cannot be zero.
Possible first digits:
1, 2, 3, ..., 9
Therefore:
for (int d = 1; d <= 9; d++) {
dp[1][d] = 1;
}
Meaning:
One-digit number with sum 1 → only 1
One-digit number with sum 2 → only 2
...
One-digit number with sum 9 → only 9
DP Table Example
Suppose:
n = 2
sum = 4
Initial table:
Now compute:
dp[2][4]
Last digit can be:
0, 1, 2, 3, 4
Therefore:
dp[2][4]
=
dp[1][4]
+
dp[1][3]
+
dp[1][2]
+
dp[1][1]
+
dp[1][0]
=
1 + 1 + 1 + 1 + 0
=
4
Valid numbers:
13
22
31
40
Exactly 4 numbers.
Complete Code
class Solution {
public int countWays(int n, int sum) {
// Impossible case
if (sum > 9 * n || sum < 1)
return -1;
int[][] dp = new int[n + 1][sum + 1];
// Base Case
for (int d = 1; d <= 9 && d <= sum; d++) {
dp[1][d] = 1;
}
// Fill DP table
for (int i = 2; i <= n; i++) {
// Current required sum
for (int s = 0; s <= sum; s++) {
// Current digit
for (int d = 0; d <= 9; d++) {
if (s >= d) {
dp[i][s] += dp[i - 1][s - d];
}
}
}
}
return dp[n][sum] == 0 ? -1 : dp[n][sum];
}
}
Code Explanation
Step 1
if (sum > 9 * n || sum < 1)
return -1;
Maximum possible digit sum is:
9 × n
Example:
n = 2
Maximum sum:
18
If:
sum = 20
No valid number exists.
Return:
-1
Step 2
int[][] dp = new int[n + 1][sum + 1];
Create a DP table.
Rows → Number of digits
Columns → Digit sums
Step 3
for (int d = 1; d <= 9 && d <= sum; d++) {
dp[1][d] = 1;
}
Initialize one-digit numbers.
Example:
dp[1][5] = 1
because:
5
is the only one-digit number with digit sum 5.
Step 4
for (int i = 2; i <= n; i++)
Build solutions for:
2 digits
3 digits
...
n digits
Step 5
for (int s = 0; s <= sum; s++)
Try every possible required digit sum.
Step 6
for (int d = 0; d <= 9; d++)
Try every possible digit at the current position.
Step 7
if (s >= d)
Example:
Need:
sum = 4
Cannot place:
digit = 7
because:
4 - 7 < 0
So skip it.
Step 8
dp[i][s] += dp[i - 1][s - d];
This is the key DP transition.
Suppose:
Need:
3 digits
sum = 8
If the last digit is:
5
then previous digits must contribute:
8 - 5 = 3
So we add:
dp[2][3]
Repeat this for every digit from 0 to 9.
Step 9
return dp[n][sum] == 0 ? -1 : dp[n][sum];
If no valid number exists:
return -1
Otherwise:
return count
Dry Run
Input
n = 2
sum = 2
Initial DP
dp[1][1] = 1
dp[1][2] = 1
Now compute:
dp[2][2]
Try Every Last Digit
Digit = 0
Need dp[1][2]
=
1
Digit = 1
Need dp[1][1]
=
1
Digit = 2
Need dp[1][0]
=
0
All larger digits are ignored.
Total:
1 + 1 = 2
Valid numbers:
11
20
Answer
2
Complexity Analysis
Time Complexity
There are three nested loops:
n digits
sum possible sums
10 possible digits
Therefore:
O(n × sum × 10)
Since 10 is constant:
O(n × sum)
Space Complexity
The DP table stores:
(n + 1) × (sum + 1)
values.
Therefore:
O(n × sum)
Summary
The brute-force solution requires checking every n-digit number, which quickly becomes infeasible for larger values of n. Dynamic Programming provides an efficient alternative by building solutions digit by digit and reusing previously computed results. By defining dp[i][s] as the number of i-digit numbers whose digit sum equals s, we can compute the answer in O(n × sum) time and O(n × sum) space. This approach efficiently counts all valid n-digit numbers while respecting the constraint that the first digit cannot be zero.