Introduction

Counting how many times a digit k appears between 0 and N looks like a brute-force problem at first, but there is a much faster digit-by-digit solution. The key idea is to count how often k appears in the ones place, tens place, hundreds place, and so on, instead of scanning every number individually.

The Brute-Force Baseline

A direct solution is easy to write:

1def count_digit_bruteforce(n, k):
2    target = str(k)
3    total = 0
4    for value in range(n + 1):
5        total += str(value).count(target)
6    return total

This is fine for small N, but it becomes too slow when N grows large because it processes every number one by one.

Count by Position Instead

For each decimal position, we can reason about how often the digit k appears there.

At a given factor such as 1, 10, 100, and so on:

• 'higher is the part of the number to the left of the current digit'
• 'current is the digit at the current position'
• 'lower is the part to the right'

That decomposition lets us count full cycles and partial cycles of digit appearance.

Efficient Algorithm for Digits 1 Through 9

For nonzero digits, the logic is straightforward.

1def count_digit(n, k):
2    if not (0 <= k <= 9):
3        raise ValueError("k must be a digit from 0 to 9")
4    if n < 0:
5        return 0
6    if k == 0:
7        return count_zero(n)
8
9    total = 0
10    factor = 1
11
12    while factor <= n:
13        lower = n % factor
14        current = (n // factor) % 10
15        higher = n // (factor * 10)
16
17        if current < k:
18            total += higher * factor
19        elif current == k:
20            total += higher * factor + lower + 1
21        else:
22            total += (higher + 1) * factor
23
24        factor *= 10
25
26    return total

This runs in O(log N) time because it processes one digit position at a time.

Why Zero Is Special

Counting digit 0 needs special handling because leading zeros are not written in ordinary decimal representations.

For example, when counting zeros between 0 and 99, you should not pretend that 7 is written as 07 unless the problem explicitly says to use fixed-width formatting.

That means the normal position formula for digits 1 through 9 overcounts zeros.

Handling Zero Correctly

Here is one way to handle zero without counting leading zeros:

1def count_zero(n):
2    if n == 0:
3        return 1
4
5    total = 0
6    factor = 1
7
8    while factor <= n:
9        lower = n % factor
10        current = (n // factor) % 10
11        higher = n // (factor * 10)
12
13        if higher == 0:
14            break
15
16        if current == 0:
17            total += (higher - 1) * factor + lower + 1
18        else:
19            total += higher * factor
20
21        factor *= 10
22
23    return total + 1  # include the zero in the number 0

That final + 1 accounts for the number 0 itself.

Example Checks

print(count_digit(13, 1))  # 6
print(count_digit(25, 2))  # 9
print(count_digit(100, 0)) # 12

These examples are good sanity checks when validating the position-based logic.

Why the Formula Works

At each position, digits repeat in cycles. In the ones place, the pattern repeats every 10 numbers. In the tens place, it repeats every 100 numbers. The formula counts:

• complete cycles, which contribute predictably
• the incomplete tail, which depends on the current digit and lower part

That is what turns a seemingly linear scan into a logarithmic digit-analysis algorithm.

Common Pitfalls

The most common mistake is forgetting that zero needs different logic because leading zeros do not count.

Another issue is off-by-one errors in the lower + 1 part when the current digit equals k.

People also mix up “count the digit in numbers from 0 to N” with “count numbers that contain the digit.” Those are different problems.

Finally, do not default to brute force for large N if you only need the count. The position-based method is both faster and cleaner once you understand it.

Summary

• Brute force works for small inputs but scales poorly.
• The efficient method counts digit occurrences one decimal position at a time.
• Digits 1 through 9 follow a simpler counting formula than 0.
• Zero needs special handling because leading zeros are not written.
• The efficient solution runs in O(log N) time.