LeetCode //C - 233. Number of Digit One

233. Number of Digit One

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

Example 2:

Input: n = 0
Output: 0

Constraints:

• $0<=n<=10^9$

From: LeetCode
Link: 233. Number of Digit One

Solution:

Ideas:

1. Initialization:

• count keeps track of the total number of 1s.
• factor is used to represent the current digit place we are evaluating (units, tens, hundreds, etc.).

2. Loop through each digit place:

• lower_numbers: Numbers that are lower than the current digit place.
• current_digit: The digit at the current place.
• higher_numbers: Numbers that are higher than the current digit place.

3. Counting logic:

• If current_digit is 0, the count of 1s is determined by the higher digits.
• If current_digit is 1, we add the count from higher digits and the count from lower digits plus one (for the current digit itself).
• If current_digit is greater than 1, we add the count from higher digits plus one entire set of the current digit place.

4. Increment the factor: Move to the next higher digit place by multiplying the factor by 10.

Code:

int countDigitOne(int n) {
    if (n <= 0) return 0;
    
    long long count = 0;
    long long factor = 1;
    
    while (factor <= n) {
        long long lower_numbers = n - (n / factor) * factor;
        long long current_digit = (n / factor) % 10;
        long long higher_numbers = n / (factor * 10);
        
        if (current_digit == 0) {
            count += higher_numbers * factor;
        } else if (current_digit == 1) {
            count += higher_numbers * factor + lower_numbers + 1;
        } else {
            count += (higher_numbers + 1) * factor;
        }
        
        factor *= 10;
    }
    
    return count;
}