Digit Count in Range
Problem
Given a single digit d (0 to 9) and two integers low and high, count how many times the digit d occurs across all integers in the inclusive range [low, high].
d = 1, low = 1, high = 136def digits_count(d, low, high):
def count(n): # occurrences of d in 0..n
total, p = 0, 1
while p <= n:
high_part = n // (p * 10)
cur = (n // p) % 10
low_part = n % p
total += high_part * p
if cur > d:
total += p
elif cur == d:
total += low_part + 1
if d == 0:
total -= p # remove counts from leading-zero block
p *= 10
return total
return count(high) - count(low - 1)function digitsCount(d, low, high) {
function count(n) { // occurrences of d in 0..n
let total = 0, p = 1;
while (p <= n) {
const highPart = Math.floor(n / (p * 10));
const cur = Math.floor(n / p) % 10;
const lowPart = n % p;
total += highPart * p;
if (cur > d) total += p;
else if (cur === d) total += lowPart + 1;
if (d === 0) total -= p;
p *= 10;
}
return total;
}
return count(high) - count(low - 1);
}class Solution {
public int digitsCount(int d, int low, int high) {
return count(d, high) - count(d, low - 1);
}
private int count(int d, int n) { // occurrences of d in 0..n
int total = 0;
for (long p = 1; p <= n; p *= 10) {
long highPart = n / (p * 10);
long cur = (n / p) % 10;
long lowPart = n % p;
total += highPart * p;
if (cur > d) total += p;
else if (cur == d) total += lowPart + 1;
if (d == 0) total -= p;
}
return total;
}
}int countUpTo(int d, long long n) { // occurrences of d in 0..n
long long total = 0;
for (long long p = 1; p <= n; p *= 10) {
long long highPart = n / (p * 10);
long long cur = (n / p) % 10;
long long lowPart = n % p;
total += highPart * p;
if (cur > d) total += p;
else if (cur == d) total += lowPart + 1;
if (d == 0) total -= p;
}
return (int)total;
}
int digitsCount(int d, int low, int high) {
return countUpTo(d, high) - countUpTo(d, low - 1);
}Explanation
Counting a digit across a whole range is much easier if we first solve a simpler sub-problem: how many times does digit d appear in 0..n? Call that count(n). Then the answer for [low, high] is just count(high) - count(low - 1) — a classic prefix subtraction.
To build count(n) we go place by place (ones, tens, hundreds, …). At each place value p we split n into a higher part, the current digit, and a lower part. The higher part tells us how many full cycles of that place have completed, and each full cycle contributes the digit d exactly p times.
Then we handle the partial cycle by comparing the current digit to d: if cur > d we add a full p; if cur == d we add only lowPart + 1 (the count so far in this block); if smaller we add nothing. The d == 0 case subtracts p to remove leading-zero overcounting.
Example: d = 1, range [1, 13]. Digit 1 shows up in 1, 10, 12, 13 once each and in 11 twice, total 6. The formula gives count(13) - count(0) = 6.
Because we only loop over the place values of the number, the whole thing runs in time proportional to the number of digits, which is logarithmic in high.