LeetCodee

233. Number of Digit One

Jump to Solution: Python Java C++ JavaScript C#

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.

Example 1:

Input: n = 13
Output: 6
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Example 2:

Input: n = 0
Output: 0

Constraints:

  • 0 <= n <= 10⁹

Solution

Python Solution

class Solution:
    def countDigitOne(self, n: int) -> int:
        if n <= 0:
            return 0
            
        count = 0
        i = 1  # current digit position
        
        while i <= n:
            # Calculate the count of 1's at current digit position
            divider = i * 10
            quotient = n // divider
            remainder = n % divider
            
            # Count complete groups of 1's
            count += quotient * i
            
            # Count additional 1's in the current digit
            if remainder >= i * 2 - 1:
                count += i
            elif remainder >= i:
                count += remainder - i + 1
            
            i *= 10
            
        return count

Time Complexity: O(log n)

We process each digit position, and there are log₁₀(n) digits.

Space Complexity: O(1)

Only uses a constant amount of extra space.

Java Solution

class Solution {
    public int countDigitOne(int n) {
        if (n <= 0) {
            return 0;
        }
        
        int count = 0;
        long i = 1;  // Use long to avoid overflow
        
        while (i <= n) {
            // Calculate the count of 1's at current digit position
            long divider = i * 10;
            long quotient = n / divider;
            long remainder = n % divider;
            
            // Count complete groups of 1's
            count += quotient * i;
            
            // Count additional 1's in the current digit
            if (remainder >= i * 2 - 1) {
                count += i;
            } else if (remainder >= i) {
                count += remainder - i + 1;
            }
            
            i *= 10;
        }
        
        return count;
    }
}

Time Complexity: O(log n)

We process each digit position, and there are log₁₀(n) digits.

Space Complexity: O(1)

Only uses a constant amount of extra space.

C++ Solution

class Solution {
public:
    int countDigitOne(int n) {
        if (n <= 0) {
            return 0;
        }
        
        int count = 0;
        long long i = 1;  // Use long long to avoid overflow
        
        while (i <= n) {
            // Calculate the count of 1's at current digit position
            long long divider = i * 10;
            long long quotient = n / divider;
            long long remainder = n % divider;
            
            // Count complete groups of 1's
            count += quotient * i;
            
            // Count additional 1's in the current digit
            if (remainder >= i * 2 - 1) {
                count += i;
            } else if (remainder >= i) {
                count += remainder - i + 1;
            }
            
            i *= 10;
        }
        
        return count;
    }
};

Time Complexity: O(log n)

We process each digit position, and there are log₁₀(n) digits.

Space Complexity: O(1)

Only uses a constant amount of extra space.

JavaScript Solution

/**
 * @param {number} n
 * @return {number}
 */
var countDigitOne = function(n) {
    if (n <= 0) {
        return 0;
    }
    
    let count = 0;
    let i = 1;  // current digit position
    
    while (i <= n) {
        // Calculate the count of 1's at current digit position
        const divider = i * 10;
        const quotient = Math.floor(n / divider);
        const remainder = n % divider;
        
        // Count complete groups of 1's
        count += quotient * i;
        
        // Count additional 1's in the current digit
        if (remainder >= i * 2 - 1) {
            count += i;
        } else if (remainder >= i) {
            count += remainder - i + 1;
        }
        
        i *= 10;
    }
    
    return count;
};

Time Complexity: O(log n)

We process each digit position, and there are log₁₀(n) digits.

Space Complexity: O(1)

Only uses a constant amount of extra space.

C# Solution

public class Solution {
    public int CountDigitOne(int n) {
        if (n <= 0) {
            return 0;
        }
        
        int count = 0;
        long i = 1;  // Use long to avoid overflow
        
        while (i <= n) {
            // Calculate the count of 1's at current digit position
            long divider = i * 10;
            long quotient = n / divider;
            long remainder = n % divider;
            
            // Count complete groups of 1's
            count += (int)(quotient * i);
            
            // Count additional 1's in the current digit
            if (remainder >= i * 2 - 1) {
                count += (int)i;
            } else if (remainder >= i) {
                count += (int)(remainder - i + 1);
            }
            
            i *= 10;
        }
        
        return count;
    }
}

Time Complexity: O(log n)

We process each digit position, and there are log₁₀(n) digits.

Space Complexity: O(1)

Only uses a constant amount of extra space.

Approach Explanation

The solution uses a mathematical approach to count digit ones. Here's how it works:

  1. For each digit position:
    • Calculate complete groups of 1's (quotient * i)
    • Handle additional 1's in the current position
    • Move to the next digit position (multiply by 10)
  2. For each position, consider:
    • Complete groups: How many full sets of 1's occur
    • Partial groups: Additional 1's in the remainder
    • Edge cases: When remainder is large enough for all 1's

Example breakdown for n = 213:

  • Ones digit: 21 complete groups of 1's, plus 1 more (total: 22)
  • Tens digit: 2 complete groups of 10 1's, plus 4 more (total: 24)
  • Hundreds digit: 1 complete group of 100 1's (total: 100)
  • Final total: 146 ones

Key insights:

  • Pattern repeats every 10 positions
  • Need to handle overflow in some languages
  • Can be solved without converting to string
  • Mathematical approach is more efficient than counting