Write count_numbers(a: int, b: int) -> int returning how many integers x with a <= x <= b have no two adjacent digits equal when written in decimal without leading zeros.
Constraints: 0 <= a <= b <= 10**18.
count_numbers(10, 20) # 10: every number except 11
count_numbers(0, 9) # 10: single digits have no neighbours
count_numbers(120, 125) # 5: all but 122
count_numbers(100, 100) # 0: "100" has two 0s side by side
Looping over the range is out of the question; aim for time polynomial in the number of digits.
Careful: leading zeros are not written, so 5 counts (it is not 005).
Show hint
Count f(x) for 0..x and answer f(b) - f(a - 1). For f, build the number from the left, memoizing on the position, the previous digit, whether you're still bounded by x's prefix, and whether a non-zero digit has been placed yet.