Problem Description

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

For example, if n = 13, then the numbers from 0 to 13 are: 0, 1, 2, ..., 13. The digit '1' appears in: 1, 10, 11, 12, and 13. The total count is 6.

• You are given a single integer input n.
• Your output should be the count of digit '1' in all numbers from 0 to n (inclusive).
• Constraints: 0 ≤ n ≤ 2,147,483,647.

Thought Process

The first idea that may come to mind is a brute-force approach: check every number from 1 to n, convert it to a string, and count how many times the digit '1' appears. While this works for small n, it becomes very slow for large values (up to 2 billion).

To optimize, we need to avoid examining every number individually. Instead, we can look for patterns in how often the digit '1' appears in each digit position (ones, tens, hundreds, etc.). This leads us to a mathematical approach that counts '1's position by position, leveraging the regularity of how numbers are constructed in base-10.

Solution Approach

We solve the problem digit by digit, counting how many times '1' appears at each digit position (units, tens, hundreds, etc.). The key insight is to analyze the contribution of each digit position across the entire range.

1. Iterate over each digit position: For each position (ones, tens, hundreds, ...), we calculate how many times '1' can appear there.
2. Divide n: For digit position k (e.g., 1 for units, 10 for tens), we split n into:
   • higher = n // (k * 10): The part to the left of the current digit.
   • current = (n // k) % 10: The current digit.
   • lower = n % k: The part to the right of the current digit.
3. Count the '1's for this position:
   • If current == 0, the count is higher * k.
   • If current == 1, the count is higher * k + lower + 1.
   • If current > 1, the count is (higher + 1) * k.
4. Sum up all counts: Add the count for each digit position to a running total.
5. Repeat for higher positions: Increase k by a factor of 10 each time until k > n.

This approach efficiently counts '1's without examining every single number, making it suitable for very large n.

Example Walkthrough

Let's walk through the process for n = 13:

1. Ones place (k = 1):
   • higher = 13 // 10 = 1
   • current = (13 // 1) % 10 = 3
   • lower = 13 % 1 = 0
   • Since current > 1, count = (1 + 1) * 1 = 2
2. Tens place (k = 10):
   • higher = 13 // 100 = 0
   • current = (13 // 10) % 10 = 1
   • lower = 13 % 10 = 3
   • Since current == 1, count = 0 * 10 + 3 + 1 = 4
3. Sum: 2 (ones place) + 4 (tens place) = 6

This matches the manual count: the digit '1' appears 6 times between 0 and 13.

Time and Space Complexity

• Brute-force approach: For each number from 1 to n, count '1's. This is O(n \cdot d), where d is the number of digits in n. For large n, this is very slow.
• Optimized approach: We only loop through the digit positions (logarithmic in n). The time complexity is O(\log_{10} n) because we process each digit position once.
• Space complexity: Both approaches use O(1) extra space.

Code Implementation

class Solution:
    def countDigitOne(self, n: int) -> int:
        count = 0
        k = 1
        while k <= n:
            higher = n // (k * 10)
            current = (n // k) % 10
            lower = n % k
            if current == 0:
                count += higher * k
            elif current == 1:
                count += higher * k + lower + 1
            else:
                count += (higher + 1) * k
            k *= 10
        return count
      

class Solution {
public:
    int countDigitOne(int n) {
        int count = 0;
        long k = 1;
        while (k <= n) {
            int higher = n / (k * 10);
            int current = (n / k) % 10;
            int lower = n % k;
            if (current == 0) {
                count += higher * k;
            } else if (current == 1) {
                count += higher * k + lower + 1;
            } else {
                count += (higher + 1) * k;
            }
            k *= 10;
        }
        return count;
    }
};
      

class Solution {
    public int countDigitOne(int n) {
        int count = 0;
        long k = 1;
        while (k <= n) {
            int higher = (int)(n / (k * 10));
            int current = (int)((n / k) % 10);
            int lower = (int)(n % k);
            if (current == 0) {
                count += higher * k;
            } else if (current == 1) {
                count += higher * k + lower + 1;
            } else {
                count += (higher + 1) * k;
            }
            k *= 10;
        }
        return count;
    }
}
      

var countDigitOne = function(n) {
    let count = 0;
    let k = 1;
    while (k <= n) {
        let higher = Math.floor(n / (k * 10));
        let current = Math.floor(n / k) % 10;
        let lower = n % k;
        if (current === 0) {
            count += higher * k;
        } else if (current === 1) {
            count += higher * k + lower + 1;
        } else {
            count += (higher + 1) * k;
        }
        k *= 10;
    }
    return count;
};
      

Summary

Instead of brute-forcing through every number, we count the occurrences of '1' at each digit position across all numbers up to n. By breaking the problem down digit by digit, we achieve a logarithmic time solution that is both efficient and elegant. This approach demonstrates the power of mathematical reasoning and pattern recognition in algorithm design.