N digit numbers with digit sum S
Find out the number of N
digit numbers, whose digits on being added equals to a given number S
. Note that a valid number starts from digits 1-9
except the number 0
itself. i.e. leading zeroes are not allowed.
Since the answer can be large, output answer modulo 1000000007
N = 2, S = 4
Valid numbers are {22, 31, 13, 40}
Hence output 4
.
public class Solution {
private long MOD = 1000000007L;
public int solve(int n, int sum) {
long[][] dp = new long[n + 1][sum + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= sum; j++) {
dp[i][j] = -1;
}
}
long count = 0;
// For first digit we can only take 1->9
for (int i = 1; i <= 9; i++) {
if (sum - i >= 0) {
count += recursion(n - 1, sum - i, dp) % MOD;
}
}
return (int) (count % MOD);
}
private long recursion(int n, int sum, long[][] dp) {
if (n == 0) {
return sum == 0 ? 1 : 0;
}
if (dp[n][sum] != -1)
return dp[n][sum];
long count = 0;
for (int i = 0; i <= 9; i++) {
if (sum - i >= 0) {
count += recursion(n - 1, sum - i, dp);
}
}
dp[n][sum] = count % MOD;
return dp[n][sum];
}
}
Last updated