Digit Count in Range solution and explanation
3 more videos on this problem
The problem
Given a single-digit integer d and two integers low and high, return the number of times that d occurs as a digit in all integers in the inclusive range [low, high].
Example 1:
Input: d = 1, low = 1, high = 13 Output: 6 Explanation: The digit d = 1 occurs 6 times in 1, 10, 11, 12, 13. Note that the digit d = 1 occurs twice in the number 11.
Example 2:
Input: d = 3, low = 100, high = 250 Output: 35 Explanation: The digit d = 3 occurs 35 times in 103,113,123,130,131,...,238,239,243.
Constraints:
0 <= d <= 91 <= low <= high <= 2 * 108
Approach overview
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.
Solution
class Solution:
def digitsCount(self, d: int, low: int, high: int) -> int:
return self.f(high, d) - self.f(low - 1, d)
def f(self, n, d):
@cache
def dfs(pos, cnt, lead, limit):
if pos <= 0:
return cnt
up = a[pos] if limit else 9
ans = 0
for i in range(up + 1):
if i == 0 and lead:
ans += dfs(pos - 1, cnt, lead, limit and i == up)
else:
ans += dfs(pos - 1, cnt + (i == d), False, limit and i == up)
return ans
a = [0] * 11
l = 0
while n:
l += 1
a[l] = n % 10
n //= 10
return dfs(l, 0, True, True)class Solution {
private int d;
private int[] a = new int[11];
private int[][] dp = new int[11][11];
public int digitsCount(int d, int low, int high) {
this.d = d;
return f(high) - f(low - 1);
}
private int f(int n) {
for (var e : dp) {
Arrays.fill(e, -1);
}
int len = 0;
while (n > 0) {
a[++len] = n % 10;
n /= 10;
}
return dfs(len, 0, true, true);
}
private int dfs(int pos, int cnt, boolean lead, boolean limit) {
if (pos <= 0) {
return cnt;
}
if (!lead && !limit && dp[pos][cnt] != -1) {
return dp[pos][cnt];
}
int up = limit ? a[pos] : 9;
int ans = 0;
for (int i = 0; i <= up; ++i) {
if (i == 0 && lead) {
ans += dfs(pos - 1, cnt, lead, limit && i == up);
} else {
ans += dfs(pos - 1, cnt + (i == d ? 1 : 0), false, limit && i == up);
}
}
if (!lead && !limit) {
dp[pos][cnt] = ans;
}
return ans;
}
}class Solution {
public:
int d;
int a[11];
int dp[11][11];
int digitsCount(int d, int low, int high) {
this->d = d;
return f(high) - f(low - 1);
}
int f(int n) {
memset(dp, -1, sizeof dp);
int len = 0;
while (n) {
a[++len] = n % 10;
n /= 10;
}
return dfs(len, 0, true, true);
}
int dfs(int pos, int cnt, bool lead, bool limit) {
if (pos <= 0) {
return cnt;
}
if (!lead && !limit && dp[pos][cnt] != -1) {
return dp[pos][cnt];
}
int up = limit ? a[pos] : 9;
int ans = 0;
for (int i = 0; i <= up; ++i) {
if (i == 0 && lead) {
ans += dfs(pos - 1, cnt, lead, limit && i == up);
} else {
ans += dfs(pos - 1, cnt + (i == d), false, limit && i == up);
}
}
if (!lead && !limit) {
dp[pos][cnt] = ans;
}
return ans;
}
};func digitsCount(d int, low int, high int) int {
f := func(n int) int {
a := make([]int, 11)
dp := make([][]int, 11)
for i := range dp {
dp[i] = make([]int, 11)
for j := range dp[i] {
dp[i][j] = -1
}
}
l := 0
for n > 0 {
l++
a[l] = n % 10
n /= 10
}
var dfs func(int, int, bool, bool) int
dfs = func(pos, cnt int, lead, limit bool) int {
if pos <= 0 {
return cnt
}
if !lead && !limit && dp[pos][cnt] != -1 {
return dp[pos][cnt]
}
up := 9
if limit {
up = a[pos]
}
ans := 0
for i := 0; i <= up; i++ {
if i == 0 && lead {
ans += dfs(pos-1, cnt, lead, limit && i == up)
} else {
t := cnt
if d == i {
t++
}
ans += dfs(pos-1, t, false, limit && i == up)
}
}
if !lead && !limit {
dp[pos][cnt] = ans
}
return ans
}
return dfs(l, 0, true, true)
}
return f(high) - f(low-1)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Digit Counting | O(n log n) | O(1) | Useful for small ranges or verifying correctness during development |
| Digit DP / Positional Counting | O(log n) | O(log n) | Optimal solution for large ranges where iterating through numbers is infeasible |
Frequently asked questions
Is Digit Count in Range easy or hard?
Digit Count in Range is considered a Hard problem because it requires understanding digit DP or positional digit counting. The brute force idea is simple, but designing the O(log n) mathematical solution requires deeper insight into number patterns.
Digit Count in Range Python/Java solution
Implement a helper function that counts occurrences of digit d from 0 to x using positional math. Call it for high and low-1, then subtract. The same logic works across Python, Java, C++, and Go since it only involves arithmetic operations and loops.
How to solve Digit Count in Range in O(log n)?
Compute a helper function count(x, d) that counts occurrences of digit d in numbers from 0 to x. Iterate through each digit position (units, tens, hundreds) and calculate contributions using the digits to the left and right. The final answer is count(high, d) minus count(low - 1, d).
What is the best approach for Digit Count in Range?
The most efficient approach uses digit DP or positional digit counting. Instead of iterating through every number, compute how many times digit d appears from 0 to high and subtract the count from 0 to low-1. This reduces the complexity to O(log n), proportional to the number of digits.
Is Digit Count in Range asked at Google/Amazon/Meta?
Digit counting and digit DP problems frequently appear in interviews at companies like Google, Amazon, and Meta. They test mathematical reasoning, number decomposition, and dynamic programming patterns over digit positions.
What data structure is used in Digit Count in Range?
The solution mainly relies on mathematical digit decomposition and sometimes a small DP table or digit array. No heavy data structures are required; the algorithm operates on digits of the number and positional calculations.
What is the time complexity of Digit Count in Range?
The optimal digit DP or positional counting solution runs in O(log n) time because it processes each digit position of the number once. Brute force solutions require O((high - low) * log n) time since each number and its digits must be examined.