Count Arrays by Digit Sums
HardDynamic Programming ยท Microsoft
Given a list required of target digit sums and an integer limit, count the arrays result of the same length where 1 <= result[i] <= limit, the digit sum of result[i] equals required[i], and result[i] <= result[i + 1] (equal neighbours are allowed). The digit sum of a number is the sum of its decimal digits.
Return the count modulo 10^9 + 7.
Example 1
- Input:
- required = [2, 3], limit = 30
- Output:
- 9
- Explanation
- The candidates are 2, 11, 20 for the first position and 3, 12, 21, 30 for the second; 2 pairs with four, 11 with three and 20 with two.
Example 2
- Input:
- required = [1, 1], limit = 10
- Output:
- 3
- Explanation
- Only 1 and 10 have digit sum 1, giving (1, 1), (1, 10) and (10, 10).
Example 3
- Input:
- required = [9, 1], limit = 10
- Output:
- 1
Constraints
1 <= required.length <= 20001 <= required[i] <= 501 <= limit <= 10000