LeetCode Problem 233

Difficulty: 🔴 Hard
Topics: Math, Dynamic Programming, Recursion

Solution

LeetCode 233 - Number of Digit One

Problem Statement

Given a non-negative integer n, we must count how many times the digit 1 appears in every number from 0 through n, inclusive.

The important detail is that we are not counting how many numbers contain the digit 1. Instead, we are counting the total number of individual 1 digits across the entire range.

For example, if n = 13, the numbers containing 1 are:

• 1
• 10
• 11
• 12
• 13

The total number of 1 digits is:

• 1 contributes 1
• 10 contributes 1
• 11 contributes 2
• 12 contributes 1
• 13 contributes 1

So the answer is 6.

The input is a single integer n, where:

0 <= n <= 10^9

This constraint is very important because it tells us that iterating through every number and counting digits directly may become too slow. A brute-force solution would potentially process one billion numbers, which is not practical.

The problem guarantees that the input is non-negative, so we do not need to handle negative integers.

Several edge cases are important:

• n = 0, there are no 1 digits at all.
• Numbers like 9, where no multi-digit logic exists yet.
• Numbers like 10, where a new digit position appears.
• Numbers like 11, where multiple 1s appear in the same number.
• Numbers like 100, 1000, or 10000, where digit boundaries change.
• Very large values near 10^9, where efficiency matters significantly.

Approaches

Brute Force Approach

The most straightforward solution is to iterate through every integer from 0 to n, convert each number into a string, and count how many characters equal '1'.

For example:

• Convert 1 to "1" and count one occurrence.
• Convert 11 to "11" and count two occurrences.
• Continue until reaching n.

This approach is easy to understand and obviously correct because it explicitly examines every digit of every number.

However, it is far too slow for large inputs. If n = 10^9, we would process one billion numbers, and each conversion plus digit scan costs additional time.

Optimal Mathematical Digit Counting

The key insight is that digits follow repeating patterns.

Instead of examining every number individually, we can count how many times the digit 1 appears at each decimal position independently.

Consider the ones place:

• From 0 to 9, the digit 1 appears once.
• From 10 to 19, it appears once again in the ones place.
• Every block of 10 numbers contributes exactly one 1 in the ones position.

Now consider the tens place:

• From 10 to 19, the tens digit is 1 for 10 consecutive numbers.
• From 110 to 119, the same pattern repeats.
• Every block of 100 numbers contributes 10 occurrences of 1 in the tens position.

This repeating structure allows us to count occurrences mathematically instead of explicitly iterating through all numbers.

For every digit position:

• Split the number into higher digits, current digit, and lower digits.
• Use these pieces to determine how many full cycles of 1s exist at that position.
• Add partial contributions depending on the current digit.

This reduces the complexity dramatically.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(1)	Iterates through every number and counts digits
Optimal	O(log n)	O(1)	Counts contributions digit by digit mathematically

Algorithm Walkthrough

We process one digit position at a time.

Suppose we are examining a position represented by factor.

• factor = 1 means ones place
• factor = 10 means tens place
• factor = 100 means hundreds place

For each position, we divide the number into three parts:

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

For example, if:

n = 31456
factor = 100

Then:

higher = 314
current = 5
lower = 56

We compute these values as:

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

Step-by-step Algorithm

1. Initialize count = 0 and factor = 1.
2. While factor <= n, process the current digit position.
3. Compute:

• higher
• current
• lower

4. If current == 0:

The number of 1s contributed by this position is:

higher * factor

This happens because only complete cycles contribute. 5. If current == 1:

The contribution becomes:

higher * factor + lower + 1

The complete cycles contribute higher * factor, and the partial cycle contributes lower + 1. 6. If current > 1:

Then the current position has already completed one additional full cycle of 1s:

(higher + 1) * factor

7. Add the contribution to count.
8. Multiply factor by 10 to move to the next digit position.
9. Continue until all digit positions are processed.

Why it works

Every decimal position follows a predictable repeating cycle. By analyzing each digit independently, we can determine exactly how many numbers contribute a 1 at that position. Since every occurrence of 1 belongs to exactly one digit position, summing all positional contributions produces the total count correctly.

Python Solution

class Solution:
    def countDigitOne(self, 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

The implementation follows the mathematical observation directly.

The variable factor identifies the digit position currently being processed. Starting with 1 means we begin at the ones place.

Inside the loop, the number is partitioned into:

• higher
• current
• lower

These components determine how many complete and partial cycles contribute 1s at the current position.

The three conditional branches correspond to the three possible states of the current digit:

• 0
• 1
• greater than 1

Each case uses a formula derived from the digit cycle behavior.

Finally, we multiply factor by 10 to move to the next digit position.

Because the number of decimal digits is at most 10 for the given constraints, the loop runs only a small number of times.

Go Solution

func countDigitOne(n int) int {
    count := 0
    factor := 1

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

        if current == 0 {
            count += higher * factor
        } else if current == 1 {
            count += higher*factor + lower + 1
        } else {
            count += (higher + 1) * factor
        }

        factor *= 10
    }

    return count
}

The Go implementation is nearly identical to the Python version because the algorithm relies only on integer arithmetic.

Go uses explicit variable declarations with :=, while Python uses dynamic typing.

The problem constraints ensure that integer overflow is not an issue for standard Go int on LeetCode environments.

Worked Examples

Example 1

Input: n = 13

We process digit positions one by one.

factor	higher	current	lower	Contribution	Total
1	1	3	0	(1 + 1) × 1 = 2	2
10	0	1	3	0 × 10 + 3 + 1 = 4	6

Final answer:

6

The counted numbers are:

1
10
11
12
13

Total number of 1s:

1 + 1 + 2 + 1 + 1 = 6

Example 2

Input: n = 0

The loop condition:

factor <= n

becomes:

1 <= 0

which is false immediately.

So the function returns:

0

Additional Example

Input: n = 99

factor	higher	current	lower	Contribution	Total
1	9	9	0	(9 + 1) × 1 = 10	10
10	0	9	9	(0 + 1) × 10 = 10	20

Final answer:

20

This is correct because:

• Ones place contributes 10 times
• Tens place contributes 10 times

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	One iteration per digit position
Space	O(1)	Only a few integer variables are used

The algorithm processes each decimal digit exactly once. Since a number with value n has approximately log10(n) digits, the total runtime is logarithmic.

The memory usage remains constant because no additional data structures are allocated.

Test Cases

solution = Solution()

assert solution.countDigitOne(0) == 0          # minimum input
assert solution.countDigitOne(1) == 1          # single one
assert solution.countDigitOne(5) == 1          # only one occurrence
assert solution.countDigitOne(9) == 1          # largest single digit
assert solution.countDigitOne(10) == 2         # transition to two digits
assert solution.countDigitOne(11) == 4         # repeated ones
assert solution.countDigitOne(13) == 6         # provided example
assert solution.countDigitOne(19) == 12        # full teen range
assert solution.countDigitOne(20) == 12        # no additional one
assert solution.countDigitOne(99) == 20        # balanced two-digit cycles
assert solution.countDigitOne(100) == 21       # transition to three digits
assert solution.countDigitOne(101) == 23       # ones in multiple positions
assert solution.countDigitOne(110) == 33       # repeated positional ones
assert solution.countDigitOne(111) == 36       # dense one distribution
assert solution.countDigitOne(999) == 300      # complete three-digit cycles
assert solution.countDigitOne(1000) == 301     # boundary increase
assert solution.countDigitOne(10000) == 4001   # larger power of ten

Test	Why
n = 0	Validates empty range behavior
n = 1	Smallest non-zero case
n = 9	Single digit upper boundary
n = 10	Tests first digit expansion
n = 11	Multiple 1s in same number
n = 13	Provided example
n = 99	Complete two-digit cycle
n = 100	Power-of-ten transition
n = 111	Dense concentration of 1s
n = 999	Full repeating pattern
n = 10000	Large positional transition

Edge Cases

Edge Case 1, n = 0

This is the smallest possible input. A common bug is accidentally counting the digit 1 in the number 0 itself or incorrectly entering the loop once.

The implementation handles this correctly because the loop condition:

factor <= n

fails immediately when n = 0.

Edge Case 2, Numbers Containing Multiple 1s

Values like 11, 111, or 1111 are important because the same number contributes multiple occurrences of the digit 1.

A flawed implementation might count only whether a number contains 1, instead of counting every occurrence independently.

This algorithm avoids that mistake because it processes each digit position separately and sums all contributions independently.

Edge Case 3, Powers of Ten

Inputs like 10, 100, and 1000 are common sources of off-by-one errors.

For example:

n = 100

must correctly count:

• the 1 in 1
• all teen numbers
• the 1 in 100

The formula for the current == 1 case:

higher * factor + lower + 1

correctly accounts for the partial cycle contribution and prevents missing or double-counting boundary values.

Edge Case 4, Very Large Inputs

The constraint allows values up to 10^9.

A brute-force approach would be far too slow because it would require processing billions of digits.

The mathematical counting approach scales efficiently because it examines only the decimal positions, which is at most 10 iterations for the given constraints.