Number of Digit One

Number of Digit One

What is this problem about?

The Number of Digit One problem asks you to count the total number of digit '1' appearances in all numbers from 1 to n inclusive. For example, n=13: numbers 1,10,11,12,13 contain digits 1,1,1,2,1,1 = 6 ones total. This hard coding problem uses positional digit counting with math.

Why is this asked in interviews?

Microsoft, Meta, Amazon, Google, and Bloomberg ask this because it tests systematic positional reasoning — computing the contribution of digit 1 at each decimal position independently. The math, recursion, and dynamic programming interview pattern is demonstrated, and the elegant per-digit formula is the key insight.

Algorithmic pattern used

Per-position contribution formula. For each digit position (ones, tens, hundreds, ...), compute how many times digit '1' appears at that position in numbers 1 to n. For position representing factor (1, 10, 100, ...): let higher = n / (factor * 10), current = (n / factor) % 10, lower = n % factor. Contribution: if current > 1: (higher+1)*factor; if current == 1: higher*factor + lower + 1; if current == 0: higher*factor. Sum all positions.

Example explanation

n=13. Positions: ones (factor=1), tens (factor=10).

• Ones: higher=1, current=3, lower=0. current>1 → (1+1)*1=2. (Numbers with 1 in ones place: 1,11).
• Tens: higher=0, current=1, lower=3. current=1 → 0*10+3+1=4. (Numbers with 1 in tens place: 10,11,12,13). Total = 2+4 = 6 ✓.

Common mistakes candidates make

• Summing digit 1s for each number individually (O(n log n), too slow).
• Incorrect formula for the current == 1 case (must add lower + 1, not just lower).
• Off-by-one in the "higher" or "lower" computation.
• Not handling all decimal positions (stopping too early).

Interview preparation tip

Digit counting problems use the "fix one digit, count how many times it appears at that position" technique. Derive the formula from small examples: how many numbers 1-99 have a 1 in the tens position? (10-19 = 10 numbers). How many 1-143 have a 1 in the hundreds position? (100-143 = 44 numbers). Build the general formula from these cases. This technique generalizes to counting any specific digit from 1 to n.