Write count_digit_one(n: int) -> int returning how many times the digit 1 is written when you write out every integer from 0 to n inclusive.
Constraints: 0 <= n <= 10**18, so looping over the numbers is out of the question.
count_digit_one(13) # 6: the 1s in 1, 10, 11 (twice), 12, 13
count_digit_one(0) # 0
count_digit_one(100) # 21
Aim for time polynomial in the number of digits of n.
Show hint
Either build the numbers digit by digit from the left, tracking whether the prefix still equals n's prefix and memoizing how many completions (and 1s) each state has, or count directly, for each power of ten p, how many numbers in 0..n have a 1 in that position, from n // (10 * p), n // p % 10 and n % p.