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.
Solution:
Time: O(AB) Space: O(AB)
public class Solution { public int solve(int A, int B) { // dp[i][j] = numbers with i digits that sums to j // dp[i][j] += dp[i - 1][j - 9 ~ j - 0] // dp[1][0-9] = 1, dp[i > 1][0] = 0 // dp[A][B] int MOD = 1000000007; long[][] dp = new long[A + 1][B + 1]; for (int i = 1; i <= A; i ++) { for (int j = 0; j <= B; j ++) { if (i == 1 && j <= 9) { dp[i][j] = 1; } else if (j == 0) { dp[i][j] = 0; } else { for (int k = 0; k <= 9; k ++) { if (j - k > 0) { dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD; } } } } } // for (long[] arr : dp) { // System.out.println(Arrays.toString(arr)); // } return (int) (dp[A][B] % MOD); } }