Implement count_digit_sum(n: int, s: int) -> int: how many integers x with 0 <= x <= n have digits that add up to exactly s?
count_digit_sum(20, 2) # 3 2, 11, 20
count_digit_sum(100, 1) # 3 1, 10, 100
count_digit_sum(5, 0) # 1 just 0
Constraints: 0 <= n <= 10**18, 0 <= s <= 200. Looping over every x is hopeless for large n; the tests call your function with n near 10**18.
Show hint
build x one digit at a time from the left, memoizing on (position, tight, sum still needed), where tight means "the digits so far equal n's prefix", so the next digit may go only up to n's digit there (otherwise up to 9).