Count Numbers with Digit Sum
MediumDynamic Programming · Cisco
Given two integers x and y, count how many integers v with 0 <= v <= x have a decimal digit sum equal to y. The digit sum of v is the sum of the digits in its usual decimal form, so the digit sum of 0 is 0 and the digit sum of 305 is 3 + 0 + 5 = 8.
Return that count. If no such integer exists, return -1 instead of 0.
x can be as large as 10^15, so checking every number up to x is far too slow.
Example 1
- Input:
- x = 135, y = 9
- Output:
- 14
- Explanation
- The qualifying numbers are 9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 108, 117, 126 and 135. The bound is inclusive, so 135 itself counts.
Example 2
- Input:
- x = 20, y = 2
- Output:
- 3
- Explanation
- Only 2, 11 and 20 have digits that add up to 2.
Example 3
- Input:
- x = 5, y = 10
- Output:
- -1
- Explanation
- Every number from 0 to 5 has a digit sum of at most 5, so no number qualifies and the answer is -1.
Constraints
0 <= x <= 10^150 <= y <= 150