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 $1, 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$.
Hints
- Instead of iterating over every number, think about each digit position independently -- how many numbers in $[1, N]$ have a particular digit at the hundreds place?
- Decompose $N$ at each position into a high part, the current digit, and a low part. The count depends on whether the current digit is less than, equal to, or greater than $d$.
- For $d = 0$, the same formula overcounts because it includes leading zeros. Subtract exactly $10^i$ (one place value) at each position $i$ to correct for this.
Worked Solution
How to Think About It: The brute-force approach -- iterate through every number and count digits -- is $O(N \log N)$, which is hopeless for $N = 10^{18}$. The key insight is to think about each digit position independently. For a given position (ones, tens, hundreds, ...), you can compute exactly how many numbers in $[1, N]$ have digit $d$ in that position using simple arithmetic on the digits of $N$ itself. This gives you an $O(\log N)$ algorithm with $O(1)$ space.
Quick Estimate (warm-up): Count the digit $4$ in $1$ through $1000$. Consider a three-digit template $\_ \_ \_$ representing numbers $000$ to $999$ (we will think of all numbers as three-digit with leading zeros for now). There are $1000$ numbers and $3$ digit positions, so $3000$ total digit slots. By symmetry each digit $0$-$9$ occupies exactly $1/10$ of those slots, giving $300$ occurrences of each digit. So digit $4$ appears exactly $300$ times in $\{0, 1, \ldots, 999\}$. The number $1000$ contains no $4$'s, so the answer for $[1, 1000]$ is $\boxed{300}$.
Approach: Process $N$ one digit position at a time, from the most significant to the least significant. For each position, split $N$'s digits into the "high" part (digits above the current position), the "current" digit, and the "low" part (digits below).
Formal Solution:
Let $N$ have digits $a_k a_{k-1} \cdots a_1 a_0$ in base $10$. For position $i$ (where position $0$ is the ones place), define:
- $\text{high}_i = \lfloor N / 10^{i+1} \rfloor$ (the number formed by digits above position $i$)
- $\text{cur}_i = a_i$ (the digit at position $i$)
- $\text{low}_i = N \bmod 10^i$ (the number formed by digits below position $i$)
- $p = 10^i$ (the place value)
The count of times digit $d > 0$ appears at position $i$ across $[1, N]$ is:
$$\text{count}_i = \begin{cases} \text{high}_i \times p & \text{if } \text{cur}_i < d \\ \text{high}_i \times p + \text{low}_i + 1 & \text{if } \text{cur}_i = d \\ (\text{high}_i + 1) \times p & \text{if } \text{cur}_i > d \end{cases}$$
The total count is $\sum_i \text{count}_i$.
Handling $d = 0$: When $d = 0$, leading zeros must be excluded. The formula above would count leading zeros (e.g., it would count "007" as having two zeros). The fix: for position $i$, the leading-zero contribution is exactly $p$ (the numbers $0$ through $p - 1$ all have a leading zero at position $i$). So subtract $p$ from the formula for each position, which means replacing $\text{high}_i$ with $(\text{high}_i - 1)$ in the $\text{cur}_i < d$ and $\text{cur}_i > d$ cases, and adjusting accordingly:
$$\text{count}_i^{(d=0)} = \begin{cases} (\text{high}_i - 1) \times p + (\text{low}_i + 1) & \text{if } \text{cur}_i = 0 \\ \text{high}_i \times p & \text{if } \text{cur}_i > 0 \end{cases}$$
(When $\text{cur}_i = 0$, the original formula gives $\text{high}_i \times p + \text{low}_i + 1$; subtracting $p$ gives $(\text{high}_i - 1) \times p + \text{low}_i + 1$. When $\text{cur}_i > 0$, the original gives $(\text{high}_i + 1) \times p$; subtracting $p$ gives $\text{high}_i \times p$.)
Code:
```python def count_digit(N: int, d: int) -> int: """Count occurrences of digit d in [1, N], base 10.""" if N <= 0: return 0 count = 0 p = 1 # place value: 1, 10, 100, ... while p <= N: high = N // (p * 10) cur = (N // p) % 10 low = N % p if d > 0: if cur < d: count += high * p elif cur == d: count += high * p + low + 1 else: count += (high + 1) * p else: # d == 0, subtract leading zeros if cur == 0: count += (high - 1) * p + low + 1 else: count += high * p p *= 10 return count ```
Extension to base $b$: Replace every occurrence of $10$ with $b$. The formula is identical -- just use $p = b^i$ as the place value and divide/mod by $b$ instead of $10$.
```python def count_digit_base(N: int, d: int, b: int) -> int: """Count occurrences of digit d in [1, N], base b.""" if N <= 0: return 0 count = 0 p = 1 while p <= N: high = N // (p * b) cur = (N // p) % b low = N % p if d > 0: if cur < d: count += high * p elif cur == d: count += high * p + low + 1 else: count += (high + 1) * p else: if cur == 0: count += (high - 1) * p + low + 1 else: count += high * p p *= b return count ```
Complexity: Time $O(\log_b N)$ (one pass per digit position). Space $O(1)$.
Verification of warm-up: count_digit(1000, 4) returns $300$, matching our symmetry argument.
Answer: The digit $4$ appears $300$ times in $[1, 1000]$. The general algorithm processes each of the $O(\log N)$ digit positions independently, computing the contribution using the high/current/low decomposition. For $d = 0$, subtract one place value per position to exclude leading zeros. The same logic extends to any base $b$ by replacing $10$ with $b$.
Intuition
The core idea is a counting technique that shows up constantly in competitive programming and quant interviews: instead of iterating over the objects you are counting (here, the numbers $1$ to $N$), iterate over the positions where the thing you are counting can appear (here, digit positions). At each position, you can compute the contribution in $O(1)$ using the structure of the number $N$ itself. This "contribution by position" trick turns an $O(N)$ or $O(N \log N)$ brute force into an $O(\log N)$ closed-form calculation.
This pattern generalizes well beyond digit counting. Anytime you are asked "how many times does X appear across all items in a range," think about fixing the location/slot where X can appear and counting how many items put X there. In trading contexts, similar decomposition ideas appear when computing aggregate statistics over large order books or when analyzing the distribution of tick-level features across millions of price updates -- you rarely want to scan every entry when the structure lets you compute the answer directly.