Counting Digit Occurrences in a Range
Start with a warm-up: how many times does the digit $4$ appear in the decimal representations of the integers
, 2, \ldots, 1000$?
Now generalize. Given an integer $N \leq 10^{18}$ and a digit $d \in \{0, 1, \ldots, 9\}$, design an $O(\log N)$-time, $O(1)$-space algorithm that returns the total number of times digit $d$ appears across all integers in $[1, N]$.
Be explicit about the handling of $d = 0$ -- leading zeros should not be counted (e.g., the number $7$ is just "7", not "007").
Finally, extend your algorithm to work in an arbitrary base $b \geq 2$.
Open the full interactive solver, hints, and worked solution →