To solve this problem, we need to count the number of times a specific digit (d) appears in all numbers from 0 to (N). The approach involves processing each digit position (units, tens, hundreds, etc.) separately and calculating the occurrences of (d) in each position using a systematic method.

Approach

The key insight is to break down the problem into individual digit positions and compute the number of times the digit (d) appears in each position. For each position, we consider three parts of the number: the digits to the left (higher), the current digit (cur), and the digits to the right (lower). The count for each position is determined based on the value of the current digit relative to (d).

1. Higher Part: The number formed by digits to the left of the current position.
2. Current Digit: The digit at the current position.
3. Lower Part: The number formed by digits to the right of the current position.
4. Place Value: The value of the current position (1 for units, 10 for tens, etc.).

Case Handling:

• If (d = 0): Adjust for leading zeros by skipping positions where the higher part is zero.
• If the current digit > (d): Add the count from the higher part plus one multiplied by the place value.
• If the current digit == (d): Add the count from the higher part multiplied by the place value plus the lower part plus one.
• If the current digit < (d): Add the count from the higher part multiplied by the place value.

Edge Case: Include the number 0, which contributes one occurrence of (d=0).

Solution Code

def count_digit(n, d):
    count = 0
    place = 1
    while place <= n:
        higher = n // (place * 10)
        cur = (n // place) % 10
        lower = n % place

        if d == 0:
            if higher == 0:
                break
            count += (higher - 1) * place
        else:
            count += higher * place

        if cur > d:
            count += place
        elif cur == d:
            count += lower + 1

        place *= 10

    # Add the occurrence of zero itself if d is zero
    if d == 0:
        count += 1

    return count

# Example usage:
# print(count_digit(123,1))  # Should return57
# print(count_digit(100,0)) # Should return 12
# print(count_digit(0,0))   # Should return1

Explanation

Let's take an example to understand the working:

• Example: Count the number of times digit 1 appears in numbers from 0 to123.
  • Units Place: Every 10 numbers, digit1 appears once. From1-123, this is (12+1) = 13 times.
  • Tens Place: Every100 numbers, digit1 appears 10 times. From 1-123, this is (1+1)*10= 20 times.
  • Hundreds Place: Digit1 appears from100-123 →24 times.
  • Total:13+20+24=57, which is correct.

Another example: Count 0 in numbers from0 to 100 → 12 times (including the number0).

This approach efficiently computes the count in (O(\log_{10} n)) time complexity, as it processes each digit position once, making it suitable for large values of (n). The space complexity is (O(1)) since it uses a fixed number of variables.

This solution handles all cases correctly, including edge cases like (d=0) and (n=0). It is optimal and widely used for digit count problems.

作者声明:本文包含人工智能生成内容。