Digit Count in Range

Digit Count in Range

What is this problem about?

The Digit Count in Range interview question asks you to find the total number of times a specific digit $d$ (from 0 to 9) appears in all integers within the range from low to high (inclusive). For example, if $d=1$ and the range is [1, 13], the digit 1 appears in 1, 10, 11, 12, 13 (a total of 6 times, since it appears twice in 11).

Why is this asked in interviews?

Amazon frequently uses this problem to evaluate a candidate's mathematical logic and ability to solve problems without brute-force iteration. Since the range can be up to $10^9$, checking every number individually would take billions of operations. It evaluation your proficiency with Digit Dynamic Programming or mathematical combinatorial counting, which are crucial for performance-sensitive tasks.

Algorithmic pattern used

This problem is solved using Digit Dynamic Programming or a Mathematical Position-wise Counting approach.

1. The core idea is to count occurrences of $d$ up to high and subtract the occurrences up to low - 1.
2. For a given number $N$, you iterate through each decimal position (ones, tens, hundreds...).
3. For each position, you calculate how many times the digit $d$ appears based on the prefix (digits to the left), the current digit at that position, and the suffix (digits to the right).

Example explanation

Count occurrences of $d=1$ in the range [0, 25].

• Ones position: The digit 1 appears in 1, 11, 21. (3 times).
• Tens position: The digit 1 appears in 10, 11, 12, 13, 14, 15, 16, 17, 18, 19. (10 times). Total = 13. The formula involves dividing the number into N / (10^pos) and N % (10^pos) segments to count these full and partial cycles efficiently.

Common mistakes candidates make

• Brute Force: Trying to iterate through every number and convert it to a string to count digits, which is $O(N \log N)$ and fails for large inputs.
• Handling Zero: Counting the digit 0 is much harder than 1-9 because leading zeros are not usually written (e.g., we write "7" not "007").
• Off-by-one errors: Forgetting to handle the inclusive nature of the range correctly.

Interview preparation tip

Master the Digit DP interview pattern. It is a template-based approach where you define a state dp(index, current_count, is_less, is_started). This pattern solves almost all "count something in range [L, R]" problems, including counting even-digit numbers, unique-digit numbers, or specific digit frequencies.