Digit Count in Range - Solution & Explanation

Problem Overview: You are given a digit d and a range [low, high]. The task is to count how many times digit d appears in every number within that inclusive range. The challenge is handling large ranges efficiently without iterating through each number.

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

The most direct approach iterates through every integer from low to high. For each number, repeatedly extract digits using num % 10 and num // 10, and increment a counter whenever the extracted digit equals d. Since each number has up to log10(n) digits, the total work becomes O((high - low) * log n). This works for small ranges but quickly becomes too slow when the interval spans millions or billions of numbers.

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

The optimal solution counts occurrences of digit d from 0 to a number x, then computes the final result as count(high) - count(low - 1). Instead of checking each number individually, analyze each digit position (units, tens, hundreds, etc.). For a given position, determine how many full cycles of digits appear and how many extra digits contribute to the count. This approach relies on positional math and a form of digit dynamic programming where the prefix of the number constrains valid digit choices.

At each digit position, track three components: digits to the left of the current position, the digit at the current position, and digits to the right. These determine how many times digit d appears in that position across all numbers ≤ x. Special handling is required when d = 0 because leading zeros are not valid digits in the representation of a number.

This technique reduces the complexity to the number of digits in high, which is typically at most 10 for 32-bit integers. The algorithm runs in O(log n) time and uses O(log n) auxiliary space if implemented with digit arrays or recursion. The logic is rooted in math and dynamic programming patterns commonly seen in digit DP problems.

Recommended for interviews: Interviewers expect the positional counting or digit DP approach. Starting with the brute force solution demonstrates understanding of the problem, but the optimized count(high) - count(low - 1) strategy shows you recognize the mathematical structure of digit ranges and can design an O(log n) algorithm.