Introduction

Counting how many times the digit 1 appears in all integers from 1 to N looks like a brute-force problem at first. The efficient solution is more interesting: instead of inspecting every number, you count the contribution of each decimal position separately and finish in logarithmic time.

Core Sections

The brute-force approach is easy but too slow

A direct solution loops through every number, converts it to text, and counts the character 1.

1def count_ones_bruteforce(n: int) -> int:
2    total = 0
3    for value in range(1, n + 1):
4        total += str(value).count("1")
5    return total
6
7
8print(count_ones_bruteforce(13))

This returns 6, because the digit appears in 1, 10, 11, 12, and 13, with 11 contributing twice.

The problem is performance. For large N, iterating through every integer is unnecessary work. The digit pattern repeats regularly in base 10, and that repetition is what the efficient solution exploits.

Count one digit position at a time

Instead of counting by number, count by position: ones place, tens place, hundreds place, and so on. For a chosen digit position factor, split N into three parts:

• 'higher, the digits to the left of the current position'
• 'current, the digit at the current position'
• 'lower, the digits to the right of the current position'

For example, if N = 314159 and factor = 100, then:

• 'higher = 3141'
• 'current = 5'
• 'lower = 59'

Those three values are enough to determine how many times the current position contributes a 1 across the entire range.

The three counting cases

At each position, there are exactly three cases:

If current == 0, the contribution is:

• 'higher * factor'

If current == 1, the contribution is:

• 'higher * factor + lower + 1'

If current > 1, the contribution is:

• '(higher + 1) * factor'

Why does this work? Every full cycle of ten digits at the current position contributes exactly factor numbers where that digit is 1. The higher part counts complete cycles. The current digit tells you whether the partial cycle contributes none, part of a block, or a full extra block.

Efficient implementation in Python

1def count_ones(n: int) -> int:
2    if n <= 0:
3        return 0
4
5    total = 0
6    factor = 1
7
8    while factor <= n:
9        lower = n % factor
10        current = (n // factor) % 10
11        higher = n // (factor * 10)
12
13        if current == 0:
14            total += higher * factor
15        elif current == 1:
16            total += higher * factor + lower + 1
17        else:
18            total += (higher + 1) * factor
19
20        factor *= 10
21
22    return total
23
24
25print(count_ones(13))
26print(count_ones(99))
27print(count_ones(314159))

This runs in O(log N) time because the loop advances one decimal position per iteration.

Walk through N = 13

For factor = 1:

• 'higher = 1'
• 'current = 3'
• 'lower = 0'

Since current > 1, the ones-place contribution is (1 + 1) * 1 = 2. Those occurrences come from 1 and 11.

For factor = 10:

• 'higher = 0'
• 'current = 1'
• 'lower = 3'

Since current == 1, the tens-place contribution is 0 * 10 + 3 + 1 = 4. Those are 10, 11, 12, and 13.

Total: 2 + 4 = 6.

Why the method scales so well

The reason this algorithm is fast is that decimal digits repeat in predictable blocks. In the ones place, the pattern repeats every 10 numbers. In the tens place, every 100 numbers. In the hundreds place, every 1000 numbers. Once you count complete blocks and then add the partial remainder, you never need to inspect individual integers.

That makes the method effective even when N is in the millions or billions.

Common Pitfalls

• Forgetting the lower + 1 term when current == 1 causes an off-by-one error in the partial block.
• Updating factor incorrectly can make the loop skip digit positions or never terminate.
• Using the brute-force string-counting approach on large inputs often passes small tests and then times out later.
• Not handling n <= 0 explicitly can produce confusing behavior when the function is reused in edge-case-heavy code.
• Mixing up the meanings of higher, current, and lower makes the formulas look arbitrary instead of systematic.

Summary

• The naive approach counts digits one number at a time, but the efficient approach counts one position at a time.
• Each decimal position contributes according to whether the current digit is 0, 1, or greater than 1.
• The algorithm runs in O(log N) time because it examines only the number of digits in N.
• The current == 1 case is the detail most likely to produce mistakes.
• Once you understand the repeating-block idea, the formula becomes much easier to derive and remember.