Number Of Digit One

                                            
class Solution {
public:
    int countDigitOne(int n) {
        int count = 0;
        for (long long i = 1; i <= n; i *= 10) {
            long long divider = i * 10;
            count += (n / divider) * i + min(max(n % divider - i + 1, 0LL), i);
        }
        return count;
    }
};

                                            
class Solution {
    public int countDigitOne(int n) {
        int count = 0;
        for (long i = 1; i <= n; i *= 10) {
            long divider = i * 10;
            count += (n / divider) * i + Math.min(Math.max(n % divider - i + 1, 0), i);
        }
        return count;
    }
}

                                            
class Solution(object):
    def countDigitOne(self, n):
        ones, m = 0, 1
        while m <= n:
            ones += (n // (m * 10)) * m + min(max(n % (m * 10) - m + 1, 0), m)
            m *= 10
        return ones

                                            
int countDigitOne(int n) {
    int count = 0;
    for (long long i = 1; i <= n; i *= 10) {
        long long divider = i * 10;
        count += (n / divider) * i + fmin(fmax(n % divider - i + 1, 0), i);
    }
    return count;
}

                                            
var countDigitOne = function(n) {
    let count = 0;
    for (let i = 1; i <= n; i *= 10) {
        let divider = i * 10;

        count += Math.floor(n / divider) * i + // full 1s from 1 - 9, 10 - 19, etc.
                 Math.min(Math.max(n % divider - i + 1, 0), i); // partial 1s at the end
    }
    return count;
};

                                            
var countDigitOne = function(n: number): number {
    let count = 0;
    for (let i = 1; i <= n; i *= 10) {
        let divider = i * 10;
        
        count += Math.floor(n / divider) * i + Math.min(Math.max(n % divider - i + 1, 0), i);
    }
    
    return count;
};

                                            
impl Solution {
    pub fn count_digit_one(n: i32) -> i32 {
        let n = n as i64;
        let mut count = 0;
        let mut i = 1;
        
        while i <= n {
            let divider = i * 10;
            count += (n / divider) * i + std::cmp::min(i.max(0), std::cmp::max(0, n % divider - i + 1));
            i *= 10;
        }
        
        count as i32
    }
}

                                            
count_digit_one(N) ->
    count_digit_one(N, 1, 1, 0).

count_digit_one(0, _, _, Count) ->
    Count;
count_digit_one(N, Mul, Base, Count) when N >= Base ->
    Next = (N div (Base * 10)) * Base +
            min(Base, max(0, N rem (Base * 10) - Base + 1)),
    count_digit_one(N, Mul*10, Base*10, Count + Next);
count_digit_one(N, Mul, Base, Count) when N < Base ->
    Count.

To solve this coding challenge, you can break down the problem into smaller parts and detail each step involved in finding the total number of digit '1' appearing in all non-negative integers less than or equal to a given number \( n \).

Explanation

The approach is based on counting the number of '1's digit by digit. We will explore each place value (units, tens, hundreds, etc.) calculating how many times '1' appears in each place up to \( n \). This method leverages the mathematical properties of numbers to efficiently determine the count without directly iterating through each number up to \( n \). For example, given \( n = 13 \), the sequence of numbers is 0, 1, 2, ..., 13. We'll count '1's in each digit's place:

Units place : From 0 to 13, numbers with '1' in the units place are 1 and 11. We count two '1's.
Tens place : Numbers with '1' in the tens place are 10, 11, 12, and 13. We count four '1's.

Combining these, we get a total of six '1's.

This example helps us understand that for each digit's place value, we can count how often '1' appears systematically.

Detailed Steps in Pseudocode

Initialize:

ones

to store the count of '1's.
m

to indicate the current place value (start with units, i.e., 1).

Loop while \( m \) is less than or equal to \( n \):

Divide \( n \) by \( 10 \times m \) to determine the higher digits.
Find out how many full sets of the current place value fit in \( n \).
Using modulo, determine the lower digits.
Increment the count of '1's in the current place by the above computations.
Multiply
m

by 10 to move to the next higher place value.

The loop increments
m

by powers of 10, thus iterating through all place values from units to the largest place value less than or equal to \( n \).

                                            
# Pseudocode with comments
initialize ones to 0          # This will store the count of '1's
initialize m to 1             # m represents the current place value, starting with units place

# Loop over each place value until m is greater than n
while m <= n do
    higher_digits = n // (m * 10)                      # Count how many times the full groups of '10 * m' fit into n
    current_digit_contribution = (higher_digits * m)   # Calculate the contribution of '1's due to these higher digits
    
    lower_digits = n % (m * 10)                        # Remainder when n is divided by '10 * m'
    
    # Calculate additional '1's based on the leftover lower digits
    additional_ones = min(max(lower_digits - m + 1, 0), m)
    
    # Increment the number of ones based on both higher digits and current digit contributions
    ones += current_digit_contribution + additional_ones
    
    # Move to the next higher place value
    m = m * 10

return ones  # The total number of '1's counted

Through this systematic approach, each digit in the given number \( n \) is evaluated efficiently, ensuring that the entire process runs in a logarithmic time complexity relative to \( n \). This method cleverly bypasses the need to iterate over all integers up to \( n \), making it highly efficient and apt for large values of \( n \).