Generated by Codex with GPT-5

Quick facts

Problem gist

Given a non-negative integer n, the task is to count how many times the digit 1 appears when writing every number from 0 through n.

For example, from 0 to 13, the digit 1 appears in 1, 10, 11, 12, and 13. Counting each occurrence gives 6: one in 1, one in 10, two in 11, one in 12, and one in 13.

The brute-force idea is to convert every number to a string and count its 1 characters, but that costs too much when n is large. The optimal solution counts by decimal position instead: ones place, tens place, hundreds place, and so on.

Core idea

Look at one decimal place at a time. Suppose the current place value is factor, where factor = 1 means ones, 10 means tens, and 100 means hundreds.

Split n around that place:

  • higher: the digits to the left of the current place
  • current: the digit at the current place
  • lower: the digits to the right of the current place

For n = 23145 and factor = 100, the split is:

  • higher = 231
  • current = 1
  • lower = 45

Now count how many numbers from 0 to n have a 1 in this specific place.

The current place repeats in cycles. For the hundreds place, each full cycle has 1000 numbers: 000 through 999. Inside each cycle, exactly 100 numbers have a 1 in the hundreds place: 100 through 199. That pattern is why the contribution is built from higher, current, and lower.

There are three cases:

  1. If current == 0, all completed higher cycles contribute higher * factor.
  2. If current == 1, completed cycles contribute higher * factor, and the partial cycle contributes lower + 1.
  3. If current > 1, the partial cycle has already passed the full block of 1s, so the contribution is (higher + 1) * factor.

Add this contribution for every decimal place. That gives the total number of digit 1 occurrences without enumerating the numbers.

Why this is optimal

The answer depends on every decimal place of n, so an algorithm must inspect the number’s digits in some form. The place-value method does exactly one constant-time calculation per digit. It does not build strings, does not visit every number, and does not use a large dynamic programming table.

This can also be viewed as a compact digit-DP recurrence: each position’s contribution is determined by the prefix to its left, the digit at that position, and the suffix to its right. The math version just writes that recurrence directly.

Python solution

class DigitOneCounter:
    def count_up_to(self, upper_bound: int) -> int:
        if upper_bound <= 0:
            return 0

        total_ones = 0
        place_value = 1

        while place_value <= upper_bound:
            higher, current_digit, lower = self._split_around_place(
                upper_bound,
                place_value,
            )
            total_ones += self._count_ones_at_place(
                higher,
                current_digit,
                lower,
                place_value,
            )
            place_value *= 10

        return total_ones

    @staticmethod
    def _split_around_place(number: int, place_value: int) -> tuple[int, int, int]:
        higher = number // (place_value * 10)
        current_digit = (number // place_value) % 10
        lower = number % place_value
        return higher, current_digit, lower

    @staticmethod
    def _count_ones_at_place(
        higher: int,
        current_digit: int,
        lower: int,
        place_value: int,
    ) -> int:
        # Completed cycles always contribute one full block of this place value.
        completed_cycle_ones = higher * place_value

        if current_digit == 0:
            return completed_cycle_ones

        if current_digit == 1:
            return completed_cycle_ones + lower + 1

        return completed_cycle_ones + place_value


class Solution:
    def countDigitOne(self, n: int) -> int:
        return DigitOneCounter().count_up_to(n)

Correctness sketch

For a fixed decimal place place_value, numbers from 0 to n can be grouped by the digits to the left of that place. Every complete group of size place_value * 10 contains exactly place_value numbers whose current digit is 1, so the complete groups contribute higher * place_value.

Only the final partial group remains. If the current digit is 0, that partial group has not reached the block where the current digit is 1, so it contributes nothing extra. If the current digit is 1, the partial group includes exactly the suffixes from 0 through lower, so it contributes lower + 1. If the current digit is greater than 1, the whole block of place_value suffixes with current digit 1 has already appeared.

The algorithm applies this exact count independently to every decimal place. Each occurrence of digit 1 belongs to exactly one place, so summing all place contributions counts every occurrence once and only once.

Complexity

The loop runs once per decimal digit of n, so the time complexity is O(log n). The algorithm uses O(1) extra space.

Interview follow-ups

How would the solution count a digit other than 1?

For digits 2 through 9, the same cycle idea works almost unchanged. At each place, compare current_digit with the target digit. If it is smaller, only completed cycles count. If it equals the target, add lower + 1. If it is larger, add one full extra block.

Digit 0 is the special case because ordinary decimal notation does not include leading zeroes. A clean solution subtracts the leading-zero cycles at each place, often by using (higher - 1) * place_value as the completed-cycle base when counting zeroes. The core reasoning still works, but the implementation must be careful when higher == 0.

How would this count digit 1 in a range [left, right]?

Build a helper that counts digit 1 from 0 through an upper bound. Then the range answer is count_up_to(right) - count_up_to(left - 1). This works because every number below left is included in both prefix counts and cancels out.

The complexity stays O(log right), and the helper remains reusable. The main edge case is left <= 0; the helper should return 0 for negative bounds so the subtraction remains simple.

Can this be solved with recursive digit DP?

Yes. A digit-DP solution processes the digits from most significant to least significant and tracks whether the prefix is already smaller than n. It can return both the number of valid suffixes and the number of 1s contributed by those suffixes.

Digit DP is more general because it adapts well to extra constraints, such as “no adjacent equal digits” or “sum of digits is divisible by k.” For this specific problem, the place-value formula is simpler and uses less machinery because the only constraint is the upper bound.

What changes if n is too large for normal integer arithmetic?

If the language cannot store n safely in an integer type, read it as a decimal string. The same idea still applies, but higher and lower need to be represented by string slices or big integers. In Python this is unnecessary because integers are arbitrary precision, but in fixed-width languages it can matter.

A string-based implementation is more verbose and may need helper functions for adding and multiplying decimal strings. The asymptotic digit count remains logarithmic in the numeric value, but arithmetic on long strings adds extra cost per position.

How would the formula change for another base?

Replace 10 with the base. For a place value factor, a full cycle has factor * base numbers, and one target digit occupies factor numbers in that cycle. The same higher, current, and lower split works after interpreting the number in that base.

The runtime becomes O(log_base n). Counting zero still needs special handling to avoid leading-zero representations, just as it does in base ten.