# 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:

```text
1
```

appears in all integers from:

```text
0 to n
```

inclusive.

Example:

```text
n = 13
```

Numbers:

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

Digit `1` appears in:

```text
1
10
11
11
12
13
```

Total count:

```text
6
```

LeetCode examples include:

```text
Input:  n = 13
Output: 6
```

```text
Input:  n = 0
Output: 0
```

The constraint allows values up to:

```text
2 * 10^9
```

so brute force enumeration is too slow. ([leetcode.com](https://leetcode.com/problems/number-of-digit-one/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | Total number of digit `1` appearances from `0` to `n` |
| Range | Inclusive |
| Constraint | Large enough to require mathematical counting |

Function shape:

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

## Examples

Example 1:

```text
Input:  n = 13
Output: 6
```

Occurrences:

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

Total:

```text
6
```

Example 2:

```text
Input:  n = 20
Output: 12
```

Numbers contributing digit `1`:

```text
1
10
11
12
13
14
15
16
17
18
19
```

The number `11` contributes two ones.

Total:

```text
12
```

Example 3:

```text
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:

```python
count = 0

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

This works logically.

But if:

```text
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:

| Position | Value |
|---|---|
| Ones place | `1` |
| Tens place | `10` |
| Hundreds place | `100` |
| Thousands place | `1000` |

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

For example, consider the tens place from:

```text
0 to 99
```

The tens digit equals `1` for:

```text
10 to 19
```

Exactly:

```text
10 numbers
```

For the hundreds place from:

```text
0 to 999
```

the hundreds digit equals `1` for:

```text
100 to 199
```

Exactly:

```text
100 numbers
```

A repeating pattern appears.

## Position-Based Counting

For a position value:

```text
factor = 1, 10, 100, ...
```

split the number into three parts:

| Part | Meaning |
|---|---|
| `higher` | Digits left of current position |
| `current` | Current digit |
| `lower` | Digits right of current position |

Mathematically:

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

For example:

```text
n = 31456
factor = 100
```

We analyze the hundreds digit.

Then:

```text
higher = 314
current = 4
lower = 56
```

## Three Cases

The counting depends on the current digit.

### Case 1: Current Digit = 0

Example:

```text
n = 2304
factor = 100
```

Hundreds digit is `3`.

We count complete blocks.

Contribution:

$$
higher \times factor
$$

### Case 2: Current Digit = 1

Example:

```text
n = 21456
factor = 1000
```

Thousands digit is `1`.

We count:

1. Complete blocks
2. Partial block from lower digits

Contribution:

$$
higher \times factor + lower + 1
$$

### Case 3: Current Digit > 1

Example:

```text
n = 25456
factor = 1000
```

Thousands digit is `5`.

Then the partial block is fully included.

Contribution:

$$
(higher + 1) \times factor
$$

## Why the Formula Works

Consider the tens place.

Numbers repeat in cycles of:

```text
00 to 99
```

Within every cycle:

```text
10 to 19
```

contain digit `1` in the tens place.

Exactly:

```text
10 numbers
```

For the hundreds place, cycles are:

```text
000 to 999
```

Within every cycle:

```text
100 to 199
```

contain digit `1` in the hundreds place.

Exactly:

```text
100 numbers
```

In general, every full cycle contributes:

```text
factor
```

occurrences.

The formulas count:

1. Full cycles
2. Partial remaining cycle

## Algorithm

Initialize:

```python
count = 0
factor = 1
```

While:

```python
factor <= n
```

compute:

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

Then:

### If current digit is 0

```python
count += higher * factor
```

### If current digit is 1

```python
count += higher * factor + lower + 1
```

### If current digit is greater than 1

```python
count += (higher + 1) * factor
```

Then move to the next position:

```python
factor *= 10
```

## Correctness

We process each digit position independently.

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

$$
10 \times factor
$$

Within each complete cycle, digit `1` appears exactly:

$$
factor
$$

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:

```text
current = 0
```

the partial cycle contributes nothing extra.

If:

```text
current = 1
```

the partial cycle contributes:

$$
lower + 1
$$

extra numbers.

If:

```text
current > 1
```

the entire partial block contributes:

$$
factor
$$

extra numbers.

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

Therefore, the algorithm returns the correct total.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log n)` | One iteration per digit position |
| Space | `O(1)` | Constant extra memory |

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

## Implementation

```python
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:

```python
factor = 1
```

Then repeatedly analyze:

```text
1
10
100
1000
...
```

For each position:

```python
lower = n % factor
```

extracts digits to the right.

```python
current = (n // factor) % 10
```

extracts the current digit.

```python
higher = n // (factor * 10)
```

extracts digits to the left.

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

Finally:

```python
factor *= 10
```

moves to the next decimal position.

## Worked Example

Take:

```text
n = 31456
```

### Ones Place

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

Since current > 1:

$$
(3145 + 1) \times 1 = 3146
$$

### Tens Place

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

Contribution:

$$
(314 + 1) \times 10 = 3150
$$

### Hundreds Place

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

Contribution:

$$
(31 + 1) \times 100 = 3200
$$

Continue similarly for larger positions.

## Testing

```python
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()
```

| Test | Why |
|---|---|
| `0` | Minimum boundary |
| `1` | Single occurrence |
| `5` | Small range |
| `10` | Transition into two digits |
| `13` | Official example |
| `20` | Multiple teen numbers |
| `99` | Full two-digit cycles |
| `100` | Transition into three digits |
| `999` | Full three-digit cycles |