Count Digit Appearances - Solution & Explanation

Problem Overview: You receive an integer n and a digit d. The goal is to count how many times digit d appears in the decimal representation of all numbers from 0 to n.

Approach 1: Brute Force Enumeration (O(n log n) time, O(1) space)

The most direct solution iterates through every number from 0 to n. Convert each number to a string or repeatedly extract digits using % 10 and / 10. For every digit encountered, compare it with d and increment the counter. Each number has at most log10(n) digits, which leads to O(n log n) total work. This approach is useful for understanding the problem but becomes slow when n grows large.

Approach 2: Positional Digit Counting (O(log n) time, O(1) space)

A faster method analyzes each digit position independently. For a position value factor = 1, 10, 100..., split the number into three parts: higher, current, and lower. These represent the digits left of the position, the digit at the position, and the digits to the right. Using these values, you can determine how many full cycles of the digit occur at that position and adjust based on the current digit. Iterate through all positions until factor > n. Since the number of positions is log10(n), the algorithm runs in O(log n) time with constant memory.

Approach 3: Digit Dynamic Programming (O(d * 10) time, O(d) space)

For generalized counting problems—especially when constraints include digit limits or multiple queries—digit DP provides a structured approach. Traverse the digits of n from most significant to least significant while tracking whether the current prefix is restricted by the upper bound. Maintain state for the position and the number of occurrences counted so far. Although heavier than the positional formula, it easily extends to variations such as counting digits under additional constraints.

Recommended for interviews: Start by explaining the brute force scan to show understanding of the digit counting process. Then transition to the positional math approach. Interviewers usually expect the O(log n) solution because it demonstrates number decomposition and efficient counting. If the problem expands with constraints or ranges, mentioning mathematical digit analysis or digit DP shows deeper problem‑solving range.