LeetCode 233: Number of Digit One Solution in Python – A Step-by-Step Guide

What Is LeetCode 233: Number of Digit One?

In LeetCode 233: Number of Digit One, you’re given a non-negative integer n, and your task is to return the total count of the digit 1 appearing in all numbers from 1 to n inclusive. This is a step beyond simpler number problems like LeetCode 231: Power of Two, requiring a systematic way to tally digit occurrences across a range.

Problem Statement

• Input: An integer n (0 ≤ n ≤ 10^9).
• Output: The total number of digit 1’s in numbers from 1 to n.
• Rules: Count every 1 in every position of every number.

Constraints

• n: 0 to 10^9.

Examples

• Input: n = 13
• Numbers: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
• 1’s: 1, 10, 11 (two 1’s), 12, 13 → Total = 6.
• Input: n = 0
• Output: 0 (no numbers to count).
• Input: n = 20
• Numbers: 1, 2, ..., 9, 10, 11, 12, ..., 19, 20
• 1’s: 1, 10, 11 (two), 12, 13, 14, 15, 16, 17, 18, 19 → Total = 12.

Understanding the Problem: Counting Digit Ones

To solve LeetCode 233: Number of Digit One in Python, we need to count every occurrence of the digit 1 in all numbers up to n. This isn’t about queue operations like LeetCode 232: Implement Queue using Stacks—it’s a digit analysis task. Brute force (counting each number’s digits) is too slow for large n, so we need a smarter approach. We’ll explore two methods: 1. Best Solution (Digit-by-Digit Counting): O(log n) time, O(1) space—systematic and efficient. 2. Alternative Solution (Mathematical Pattern): O(log n) time, O(1) space—pattern-based insight.

Let’s start with the best solution.

Best Solution: Digit-by-Digit Counting Approach

Why This Is the Best Solution

The digit-by-digit counting approach is our top choice for LeetCode 233 because it processes each digit position systematically, calculates 1’s efficiently, and scales well with large numbers. It’s both intuitive and optimized, making it ideal for understanding and performance.

How It Works

• For each digit position (units, tens, hundreds, etc.), calculate how many times 1 appears.
• Use three components per position:
• Before: Numbers before the current digit (e.g., for 314, hundreds digit 3 → 300 numbers).
• Current: The digit itself (0, 1, or >1 affects the count).
• After: Numbers after the digit (remaining lower digits).
• Sum contributions across all positions.

Step-by-Step Example

Example 1: n = 13

• Digits: 13 (tens, units).
• Units (10^0 = 1):
• Before: 1 (10’s place).
• After: 0 (no digits after).
• Current: 3 > 1 → 1’s appear in 1-9 (1 time) + 10-13 (1 time if digit were 1, but adjusted) → 1.
• Tens (10^1 = 10):
• Before: 0.
• After: 3.
• Current: 1 = 1 → Full range 0-3 (4 numbers) → 4 + 1 (from 10-13) = 5.
• Total: 1 (units) + 5 (tens) = 6.

Example 2: n = 20

• Units: Current = 0 < 1 → 1 (1-9).
• Tens: Current = 2 > 1 → 10 (10-19) + 1 (1’s in 1-9) = 11.
• Total: 1 + 11 = 12.

Code with Detailed Line-by-Line Explanation

Here’s the Python implementation:

Copy codeclass Solution:
    def countDigitOne(self, n: int) -> int:
        # Line 1: Handle edge case
        if n <= 0:
            return 0

        # Line 2: Initialize count
        count = 0
        i = 1  # Position multiplier (1, 10, 100, ...)

        # Line 3: Process each digit position
        while i <= n:
            # Line 4: Calculate divider and parts
            divider = i * 10
            before = n // divider  # Higher digits
            current = (n // i) % 10  # Current digit
            after = n % i  # Lower digits

            # Line 5: Add 1’s from before
            count += before * i

            # Line 6: Add 1’s from current digit
            if current == 1:
                count += after + 1  # Full range up to after
            elif current > 1:
                count += i  # Full position count

            # Line 7: Move to next position
            i *= 10

        # Line 8: Return total
        return count

• Time Complexity: O(log n) – number of digits in n.
• Space Complexity: O(1) – constant space.

Alternative Solution: Mathematical Pattern Approach

Why an Alternative Approach?

The mathematical pattern approach uses a formulaic method to count 1’s by observing digit position patterns. It’s a great alternative if you enjoy deriving solutions from mathematical insights, though it’s conceptually similar to the best solution with a different lens.

How It Works

• For each digit position, compute 1’s based on:
• Full cycles of 1’s (e.g., every 10 numbers for units).
• Partial cycles based on the current digit.
• Adjust for edge cases like leading digits.

Step-by-Step Example

Example: n = 13

• Units: 13 // 10 = 1 cycle (10 numbers, 1 one) + 13 % 10 = 3, no extra 1 → 1.
• Tens: 1 (10-13 has 1 as tens digit) + 4 (10-13 lower digits) → 5.
• Total: 1 + 5 = 6.

Code for Mathematical Pattern Approach

Copy codeclass Solution:
    def countDigitOne(self, n: int) -> int:
        if n <= 0:
            return 0

        count = 0
        i = 1

        while i <= n:
            divider = i * 10
            count += (n // divider) * i  # Full cycles
            remaining = n % divider
            if remaining >= i:
                count += min(max(remaining - i + 1, 0), i)  # Partial cycle

            i *= 10

        return count

• Time Complexity: O(log n).
• Space Complexity: O(1).

Comparing the Two Solutions

• Best Solution (Digit-by-Digit Counting):
• Pros: Clear logic, efficient, easy to follow.
• Cons: Requires careful digit splitting.
• Alternative Solution (Mathematical Pattern):
• Pros: Pattern-based, insightful.
• Cons: Slightly more abstract.

The digit-by-digit method is our best for its clarity and precision.

Additional Examples and Edge Cases

Zero

• Input: n = 0
• Output: 0 (no 1’s).

Single Digit

• Input: n = 5
• Output: 1 (1 in 1-5).

Large Number

• Input: n = 100
• Output: 21 (1-9: 1, 10-19: 11, 20-99: 8, 100: 1).

Complexity Breakdown

• Digit-by-Digit:
• Time: O(log n).
• Space: O(1).
• Mathematical Pattern:
• Time: O(log n).
• Space: O(1).

Both are optimal, with digit-by-digit being more intuitive.

Key Takeaways for Beginners

• Digit Counting: Break down by position.
• Digit-by-Digit: Systematic per place value.
• Patterns: Leverage cycles and remainders.
• Python Tip: Modulo and division are key—see [Python Basics](/python/basics).

Final Thoughts: Count Ones Like a Pro

LeetCode 233: Number of Digit One in Python is a fascinating dive into digit analysis. The digit-by-digit counting solution offers a clear, efficient path, while the mathematical pattern approach provides a clever twist. Want more number challenges? Try LeetCode 191: Number of 1 Bits or LeetCode 204: Count Primes. Ready to count? Head to Solve LeetCode 233 on LeetCode and tally those 1’s today!