Count Occurrences of Digit 3 from 0 to N: Formula and Code

Counting every occurrence of digit 3 across all integers from 0 to N is not the same as counting how many of those integers contain a 3. Each digit position in each number contributes independently.

What This Problem Is Actually Asking

The task: given N, find the total number of times the digit “3” appears when you write out all integers from 0 to N.

Two facts that trip people on first contact. First, a number like 33 contributes two occurrences to the total, not one. It has tens digit 3 and ones digit 3. Second, 303 also contributes two, because its hundreds digit and ones digit are both 3. The count is a sum across all digit positions across all numbers, not a count of distinct numbers.

Verified examples across four values of N:

N	Numbers containing digit 3	Total occurrences of digit 3
10	3	1
30	3, 13, 23, 30	4
33	3, 13, 23, 30, 31, 32, 33	8
100	3, 13, 23, 30–39, 43, 53, 63, 73, 83, 93	20

Walking through N=33 step by step:

• 3 contributes 1 (ones digit is 3)
• 13 contributes 1 (ones digit is 3)
• 23 contributes 1 (ones digit is 3)
• 30 contributes 1 (tens digit is 3)
• 31 contributes 1 (tens digit is 3)
• 32 contributes 1 (tens digit is 3)
• 33 contributes 2 (both digits are 3)
• Total: 8

For N=100, the cleaner way to see it is positional. Ones-digit 3 appears in 3, 13, 23, 33, 43, 53, 63, 73, 83, 93: that is 10 occurrences. Tens-digit 3 appears in 30, 31, 32, 33, 34, 35, 36, 37, 38, 39: another 10 occurrences. The hundreds digit never reaches 3 in the range 0 to 100. Grand total: 20. The number 33 is counted once in each positional group, contributing one occurrence to the ones-position count and one to the tens-position count.

This question type shows up in campus placement evaluation tests as well as coding rounds at product and service companies. The progression from O(N log N) brute-force to O(log N) formula is exactly what distinguishes a candidate who understands number theory from one who only knows loops.

Brute-Force Approach: O(N log N)

The straightforward solution loops from 0 to N. For each number, it extracts digits one by one by repeatedly taking the remainder modulo 10 and dividing by 10.

Algorithm:

• Step 1: Set count to 0.
• Step 2: For each integer i from 1 to N, copy i into a temporary variable.
• Step 3: While the temporary variable is greater than 0, compute temp % 10. If the result equals 3, increment count.
• Step 4: Divide the temporary variable by 10 and repeat Step 3.
• Step 5: After processing all numbers, return count.

Time complexity: O(N log N). The outer loop runs N times. The inner loop processes every digit of i, which runs approximately log10(i) + 1 iterations. Summing across all i from 1 to N gives a total proportional to N log N. For N equal to one million, the inner loop runs roughly seven times per iteration on average, producing about seven million operations.

Space complexity: O(1). No extra data structures.

# Python — brute-force O(N log N)
def count_threes_brute(n):
    count = 0
    for i in range(1, n + 1):
        num = i
        while num > 0:
            if num % 10 == 3:
                count += 1
            num //= 10
    return count

print(count_threes_brute(33))   # 8
print(count_threes_brute(100))  # 20

The brute-force works correctly for any N but is impractical when N is very large. For N equal to 10^8 or higher, interviewers expect the O(log N) formula below. For N below a few hundred thousand, brute-force is fine and easier to test during an interview.

The O(log N) Positional Formula

The key insight is that each digit position is independent. The set of numbers from 0 to N that have digit 3 at the ones position has nothing to do with which numbers have digit 3 at the tens position. So we can count each position separately and add the results.

Definitions for position p (where p=0 is ones, p=1 is tens, p=2 is hundreds):

• factor = 10 raised to the power p (1, 10, 100, …)
• higher = N divided by factor × 10, using integer division (the number formed by digits above position p)
• current = (N divided by factor) modulo 10 (the digit of N at position p)
• lower = N modulo factor (the number formed by digits below position p)

Three cases for how often digit 3 appears at position p across all numbers from 0 to N:

• If current > 3: digit 3 has completed full cycles of 10 at this position. Count = (higher + 1) × factor.
• If current == 3: digit 3 is mid-cycle at this position. Count = higher × factor + lower + 1.
• If current < 3: digit 3 has not appeared yet in the current cycle. Count = higher × factor.

Why lower + 1 when current == 3? When the digit at position p is exactly 3, the contribution has two parts. The higher × factor term counts complete tens-blocks below the current leading prefix (each block contributes exactly factor occurrences of digit 3 at position p). The lower + 1 term counts the partial range in the current block: numbers from higher × factor × 10 up through N itself. That partial range contains numbers 0 through lower after the fixed prefix, giving lower + 1 numbers.

Derivation for N=100:

• Position 0 (ones): higher=10, current=0, lower=0. Since 0 < 3: count += 10 × 1 = 10. (Numbers: 3, 13, 23, 33, 43, 53, 63, 73, 83, 93.)
• Position 1 (tens): higher=1, current=0, lower=0. Since 0 < 3: count += 1 × 10 = 10. (Numbers: 30 through 39.)
• Position 2 (hundreds): higher=0, current=1, lower=0. Since 1 < 3: count += 0 × 100 = 0.
• Total: 10 + 10 + 0 = 20. ✓

Derivation for N=33:

• Position 0 (ones): higher=3, current=3, lower=0. Since current == 3: count += 3 × 1 + 0 + 1 = 4. (Numbers: 3, 13, 23, 33.)
• Position 1 (tens): higher=0, current=3, lower=3. Since current == 3: count += 0 × 10 + 3 + 1 = 4. (Numbers: 30, 31, 32, 33.)
• Total: 4 + 4 = 8. ✓

This formula is grounded in positional notation: in a base-10 number system, each digit position cycles independently through 0 to 9. Within any block of factor × 10 consecutive integers, digit 3 appears at position p exactly factor times. The formula counts full blocks via higher, then handles the partial final block separately using lower.

The same positional formula works for any target digit d from 1 to 9 by substituting d for 3 in the three-case check. For target digit 0, an additional adjustment handles the leading-zero case (a number like 100 is not written as 100 with a leading zero at the tens place).

Also see FACE Prep’s guide to time and work aptitude questions for a parallel decomposition technique applied to rate problems.

Complete Implementations in C / C++, Java, and Python

All three implementations include both approaches. Use long long in C and long in Java to handle large N without overflow. Python integers have no overflow issue.

The O(log N) version processes at most floor(log10(N)) + 1 digit positions, which is 10 iterations for N up to 10^9 and 19 for N up to 10^18 (the range of a signed 64-bit integer). A further reference with extended test cases is available on GeeksforGeeks.

/* C / C++ — both approaches */
#include <stdio.h>

/* Brute-force: O(N log N) */
int count_threes_brute(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        int num = i;
        while (num > 0) {
            if (num % 10 == 3) count++;
            num /= 10;
        }
    }
    return count;
}

/* O(log N) positional formula */
long long count_threes_fast(long long n) {
    long long count = 0;
    long long factor = 1;
    while (factor <= n) {
        long long higher  = n / (factor * 10);
        long long current = (n / factor) % 10;
        long long lower   = n % factor;
        if (current > 3)
            count += (higher + 1) * factor;
        else if (current == 3)
            count += higher * factor + lower + 1;
        else
            count += higher * factor;
        factor *= 10;
    }
    return count;
}

int main(void) {
    printf("%d\n",   count_threes_brute(33));   /* 8  */
    printf("%lld\n", count_threes_fast(33));    /* 8  */
    printf("%lld\n", count_threes_fast(100));   /* 20 */
    return 0;
}

// Java — O(log N) positional formula
public class CountDigit3 {

    public static long countThreesFast(long n) {
        long count = 0;
        long factor = 1;
        while (factor <= n) {
            long higher  = n / (factor * 10);
            long current = (n / factor) % 10;
            long lower   = n % factor;
            if (current > 3)
                count += (higher + 1) * factor;
            else if (current == 3)
                count += higher * factor + lower + 1;
            else
                count += higher * factor;
            factor *= 10;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(countThreesFast(33));    // 8
        System.out.println(countThreesFast(100));   // 20
    }
}

# Python — O(log N) positional formula
def count_threes_fast(n):
    count = 0
    factor = 1
    while factor <= n:
        higher  = n // (factor * 10)
        current = (n // factor) % 10
        lower   = n % factor
        if current > 3:
            count += (higher + 1) * factor
        elif current == 3:
            count += higher * factor + lower + 1
        else:
            count += higher * factor
        factor *= 10
    return count

assert count_threes_fast(33)  == 8
assert count_threes_fast(100) == 20
print("Assertions passed.")

The positional decomposition that drives the O(log N) formula (splitting N into higher, current, and lower at each digit position, then summing three independent cases) is a precise example of structured problem decomposition. That same pattern of breaking a large problem into independently solvable subproblems is what makes effective prompting work with LLMs. TinkerLLM is where you test that intuition at ₹299, through live LLM experiments with real inputs, not just a walkthrough.