NUHMAN.com

🧩 Problem Statement

Given a non-negative integer n, count the total number of digit 1 appearing in all numbers from 1 to n.

Example 1:

go

Input: n = 13
Output: 6
Explanation: Numbers from 1 to 13 contain six 1's in total: 1, 10, 11, 12, 13.

Example 2:

go

Input: n = 0
Output: 0

🧠 Approach

We need to find an efficient way to count how many times the digit 1 appears in all numbers from 1 to n. A direct approach that checks each number from 1 to n would be too slow, especially for larger values of n. Therefore, we use a more mathematical approach that breaks down the problem using place values.

Steps:

1. Digit-by-Digit Analysis:

• We can break down the number n digit by digit and calculate how many times the digit 1 appears at each position (units, tens, hundreds, etc.).

1. Mathematical Counting:

• For each digit in the number n, we can calculate how many numbers up to n have a 1 in that position.
• Consider the number n = 2345. We would calculate how many numbers from 1 to 2345 have a 1 in the units, tens, hundreds, etc.

1. Algorithm:

• For each digit position (starting from the rightmost):
• Find how many full sets of numbers exist where the current digit is a 1 in that place.
• Add the count of numbers where the digit at the current place is a 1.

1. Edge Case:

• If n is 0, return 0.

✅ Go Implementation

go

package main

import "fmt"

// Function to count the number of digit '1' in the numbers from 1 to n
func countDigitOne(n int) int {
    count := 0
    factor := 1
    
    for factor <= n {
        lowerNumbers := n - (n / factor) * factor
        currentDigit := (n / factor) % 10
        higherNumbers := n / (factor * 10)
        
        // Count the number of '1's contributed by the current digit position
        if currentDigit == 0 {
            count += higherNumbers * factor
        } else if currentDigit == 1 {
            count += higherNumbers * factor + lowerNumbers + 1
        } else {
            count += (higherNumbers + 1) * factor
        }
        
        // Move to the next digit position
        factor *= 10
    }
    
    return count
}

// Test the countDigitOne function
func main() {
    // Test case 1
    fmt.Println(countDigitOne(13))  // Output: 6
    
    // Test case 2
    fmt.Println(countDigitOne(0))   // Output: 0
}

📦 Example Usage

go

func main() {
    // Test case 1
    fmt.Println(countDigitOne(13)) // Output: 6
    // Test case 2
    fmt.Println(countDigitOne(0))  // Output: 0
    // Additional test cases
    fmt.Println(countDigitOne(100)) // Output: 21
    fmt.Println(countDigitOne(123)) // Output: 57
}

🧠 Explanation of the Code

• countDigitOne(n int):
• The function counts the number of times the digit 1 appears in all numbers from 1 to n by analyzing each digit position separately.
• factor is used to process each digit place (units, tens, hundreds, etc.).
• For each digit position, we calculate the number of times 1 appears in that position and add it to the total count.

Steps in Code:

1. We loop through the digits of n by increasing factor from 1, 10, 100, etc.
2. For each digit position, we calculate:

• lowerNumbers: The number formed by the digits less significant than the current digit.
• currentDigit: The digit at the current position.
• higherNumbers: The number formed by the digits more significant than the current digit.

1. Based on the value of currentDigit, we determine how many times 1 appears in that position:

• If currentDigit == 0: We only count numbers from the higher part.
• If currentDigit == 1: We count numbers from both the higher part and lower part.
• If currentDigit > 1: We count all possible numbers in this digit place.

1. After processing all digits, we return the total count.

⏱️ Time & Space Complexity

• Time Complexity: O(log n)
• The loop iterates over each digit of the number n. Since the number of digits is approximately log(n), the time complexity is logarithmic.
• Space Complexity: O(1)
• The space complexity is constant because we are using only a few variables (count, factor, etc.) to store intermediate results.

This solution efficiently counts the number of digit 1s by breaking down the problem digit by digit. The time complexity is logarithmic, making it feasible for large values of n.