Number of Digit One: Counting by Position

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

This is LeetCode 233: Number of Digit One. For example, when n = 13, the answer is 6. The numbers containing a 1 are: 1, 10, 11, 12, 13. Counting each occurrence of the digit 1, you get 1 + 1 + 2 + 1 + 1 = 6.

The brute-force approach (iterate through every number, check every digit) would be O(n log n), which is far too slow for large inputs. The key insight is that you can analyze each digit position independently and compute the total in O(log n) time.

The approach

Instead of scanning every number from 0 to n, you process each digit position (ones, tens, hundreds, and so on) separately. For each position, you split the number into three parts:

• higher: the digits above the current position
• current: the digit at the current position
• lower: the digits below the current position

For example, with n = 123 and the tens place: higher = 1, current = 2, lower = 3.

Then you apply one of three cases based on the current digit:

1. current == 0: The digit 1 never appears in this position for the current "group." Count = higher * factor.
2. current == 1: The digit 1 appears only partially through the current group. Count = higher * factor + lower + 1.
3. current >= 2: The digit 1 appears for the entire current group. Count = (higher + 1) * factor.

Sum the contributions from every position and you have the answer.

The solution

def countDigitOne(n: int) -> int:
    count = 0
    factor = 1

    while factor <= n:
        higher = n // (factor * 10)
        current = (n // factor) % 10
        lower = n % factor

        if current == 0:
            count += higher * factor
        elif current == 1:
            count += higher * factor + lower + 1
        else:
            count += (higher + 1) * factor

        factor *= 10

    return count

1. factor represents the current digit position: 1 for ones, 10 for tens, 100 for hundreds, and so on. It multiplies by 10 each iteration.
2. higher is computed by integer-dividing n by factor * 10. This gives you the digits above the current position.
3. current is extracted by dividing n by factor and taking the remainder mod 10. This isolates the single digit at the current position.
4. lower is n % factor, which captures all the digits below the current position.
5. The three-way branch handles the three cases: when the current digit is 0 (no partial group contribution), when it is exactly 1 (partial contribution from the lower digits), and when it is 2 or more (full group contribution).
6. The loop terminates when factor exceeds n, meaning there are no more digit positions to process.

Step-by-step walkthrough

Let's trace through the algorithm with n = 123.

Complexity analysis

The loop runs once per digit in n, so the number of iterations is floor(log10(n)) + 1. Each iteration does constant work. No additional data structures are needed.

Building blocks

Digit-by-digit analysis. Rather than iterating through all numbers, you iterate through digit positions. This technique reduces the problem from O(n) to O(log n) and appears whenever a problem asks you to count occurrences, patterns, or properties across a range of numbers. The core idea is that each digit position contributes independently to the total.

Higher / current / lower decomposition. Splitting a number into the portion above, at, and below a given digit position is a reusable pattern. It lets you reason about how many "full cycles" a digit has gone through (controlled by higher) and how far into the current cycle you are (controlled by lower). You will see this decomposition in other digit-counting and digit DP problems.

Case analysis on the current digit. The three cases (0, 1, and >= 2) capture the three possible relationships between the current digit and the target digit. This kind of case split is common in math problems where a boundary condition changes the counting formula. Recognizing which case applies and why prevents off-by-one errors.

Edge cases

• n = 0: There are no positive integers up to 0 that contain the digit 1. The while loop never executes since factor = 1 and 1 > 0. Returns 0.
• n = 1: Only the number 1 itself contains the digit 1. The ones place contributes 1, and the loop ends. Returns 1.
• n = 9: Numbers 1 through 9 contain exactly one occurrence of digit 1 (just the number 1). Returns 1.
• Large n (e.g., 10^9): The loop runs only 10 times (one per digit). No overflow risk in Python. The algorithm handles billion-scale inputs effortlessly.
• n with all 1s (e.g., 111): Every digit position has current == 1, so every position uses the partial formula higher * factor + lower + 1. For 111: ones = 12, tens = 12 + 1 + 1 = 14 (wait, let's compute: higher=11, current=1, lower=0, so 111+0+1=12; tens: higher=1, current=1, lower=1, so 110+1+1=12; hundreds: higher=0, current=1, lower=11, so 0*100+11+1=12). Total = 36.
• Powers of 10 (e.g., 100): The ones and tens digits are 0, so those positions use the current == 0 formula. Only the hundreds place (current = 1) contributes a partial count.

From understanding to recall

You now know how to split a number at each digit position, classify the current digit into one of three cases, and sum the contributions. The algorithm is short (under 15 lines) and runs in O(log n) time.

But during an interview, the tricky part is remembering the three formulas and why each one works. The connection between "current digit is 0, 1, or at least 2" and the counting formula needs to be automatic. Spaced repetition helps here. You solve the problem from scratch today, again in two days, then a week later. Each time you rebuild the three cases from first principles, the reasoning sticks a little deeper. After a few rounds, the decomposition and the formulas become second nature.

Related problems

• Factorial Trailing Zeroes (similar digit/factor counting approach)
• Count Primes (mathematical counting problem)
• Palindrome Number (digit-by-digit number analysis)