LeetCode 233: Number of Digit One

Problem Restatement

We are given a non-negative integer n.

We need to count how many times the digit:

1

appears in all integers from:

0 to n

inclusive.

Example:

n = 13

Numbers:

0 1 2 3 4 5 6 7 8 9 10 11 12 13

Digit 1 appears in:

1
10
11
11
12
13

Total count:

6

LeetCode examples include:

Input:  n = 13
Output: 6

Input:  n = 0
Output: 0

The constraint allows values up to:

2 * 10^9

so brute force enumeration is too slow. (leetcode.com)

Input and Output

Function shape:

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

Examples

Example 1:

Input:  n = 13
Output: 6

Occurrences:

1   -> one "1"
10  -> one "1"
11  -> two "1"
12  -> one "1"
13  -> one "1"

Total:

6

Example 2:

Input:  n = 20
Output: 12

Numbers contributing digit 1:

1
10
11
12
13
14
15
16
17
18
19

The number 11 contributes two ones.

Total:

12

Example 3:

Input:  n = 0
Output: 0

There are no digit ones.

First Thought: Count Directly

A direct solution is:

1. Loop from 0 to n.
2. Convert each number to string.
3. Count occurrences of "1".

Example:

count = 0

for x in range(n + 1):
    count += str(x).count("1")

This works logically.

But if:

n = 2 * 10^9

then iterating billions of numbers is impossible.

We need a mathematical counting method.

Key Insight

Instead of counting number by number, count digit positions independently.

For every decimal position:

we count how many times digit 1 appears in that position.

For example, consider the tens place from:

0 to 99

The tens digit equals 1 for:

10 to 19

Exactly:

10 numbers

For the hundreds place from:

0 to 999

the hundreds digit equals 1 for:

100 to 199

Exactly:

100 numbers

A repeating pattern appears.

Position-Based Counting

For a position value:

factor = 1, 10, 100, ...

split the number into three parts:

Mathematically:

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

For example:

n = 31456
factor = 100

We analyze the hundreds digit.

Then:

higher = 314
current = 4
lower = 56

Three Cases

The counting depends on the current digit.

Case 1: Current Digit = 0

Example:

n = 2304
factor = 100

Hundreds digit is 3.

We count complete blocks.

Contribution:

Case 2: Current Digit = 1

Example:

n = 21456
factor = 1000

Thousands digit is 1.

We count:

1. Complete blocks
2. Partial block from lower digits

Contribution:

Case 3: Current Digit > 1

Example:

n = 25456
factor = 1000

Thousands digit is 5.

Then the partial block is fully included.

Contribution:

Why the Formula Works

Consider the tens place.

Numbers repeat in cycles of:

00 to 99

Within every cycle:

10 to 19

contain digit 1 in the tens place.

Exactly:

10 numbers

For the hundreds place, cycles are:

000 to 999

Within every cycle:

100 to 199

contain digit 1 in the hundreds place.

Exactly:

100 numbers

In general, every full cycle contributes:

factor

occurrences.

The formulas count:

1. Full cycles
2. Partial remaining cycle

Algorithm

Initialize:

count = 0
factor = 1

While:

factor <= n

compute:

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

Then:

If current digit is 0

count += higher * factor

If current digit is 1

count += higher * factor + lower + 1

If current digit is greater than 1

count += (higher + 1) * factor

Then move to the next position:

factor *= 10

Correctness

We process each digit position independently.

For a position with value factor, numbers repeat in cycles of length:

Within each complete cycle, digit 1 appears exactly:

times in the current position.

The variable higher counts the number of complete cycles.

The variable current determines how much of the partial cycle contributes.

If:

current = 0

the partial cycle contributes nothing extra.

If:

current = 1

the partial cycle contributes:

extra numbers.

If:

current > 1

the entire partial block contributes:

extra numbers.

Summing contributions across all digit positions counts every occurrence of digit 1 exactly once.

Therefore, the algorithm returns the correct total.

Complexity

For a 32-bit integer, the loop runs at most about 10 times.

Implementation

class Solution:
    def countDigitOne(self, n: int) -> int:
        count = 0
        factor = 1

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

            if current == 0:
                count += higher * factor

            elif current == 1:
                count += higher * factor + lower + 1

            else:
                count += (higher + 1) * factor

            factor *= 10

        return count

Code Explanation

We begin with the ones place:

factor = 1

Then repeatedly analyze:

1
10
100
1000
...

For each position:

lower = n % factor

extracts digits to the right.

current = (n // factor) % 10

extracts the current digit.

higher = n // (factor * 10)

extracts digits to the left.

Then we apply the correct counting formula based on the current digit.

Finally:

factor *= 10

moves to the next decimal position.

Worked Example

Take:

n = 31456

Ones Place

factor = 1
higher = 3145
current = 6
lower = 0

Since current > 1:

Tens Place

factor = 10
higher = 314
current = 5
lower = 6

Contribution:

Hundreds Place

factor = 100
higher = 31
current = 4
lower = 56

Contribution:

Continue similarly for larger positions.

Testing

def run_tests():
    s = Solution()

    assert s.countDigitOne(0) == 0
    assert s.countDigitOne(1) == 1
    assert s.countDigitOne(5) == 1
    assert s.countDigitOne(10) == 2
    assert s.countDigitOne(13) == 6
    assert s.countDigitOne(20) == 12
    assert s.countDigitOne(99) == 20
    assert s.countDigitOne(100) == 21
    assert s.countDigitOne(999) == 300

    print("all tests passed")

run_tests()