You are given four integers: num1, num2, digit, and you need to count how many times the digit digit appears in all numbers in the inclusive range from num1 to num2.
num1 and num2 define the range (inclusive), where num1 <= num2.digit is a single-digit integer (0-9).digit appears in all numbers from num1 to num2 (inclusive), across all digits of every number.
Constraints: The function must work efficiently even if num2 is large (e.g., up to 109).
The most direct approach is to iterate through every number from num1 to num2, convert each number to a string, and count how many times digit appears. This is simple and intuitive, but it will be too slow for large ranges because it requires examining each number individually.
To optimize, we need a way to efficiently count the digit occurrences in a range without examining every single number. This leads us to digit dynamic programming (digit DP) or mathematical counting techniques, where we count how many times digit appears from 0 to N and use this to calculate the answer for any arbitrary range.
We want to efficiently count how many times digit appears from num1 to num2. The key idea is:
f(x, d) be the number of times digit d appears in all numbers from 0 to x (inclusive).[num1, num2] is f(num2, digit) - f(num1 - 1, digit).f(x, d) efficiently, we use digit position analysis:
d appears in that position across all numbers from 0 to x.
The main challenge is handling the leading zeros and the special case when digit == 0 (since numbers do not have leading zeros).
count_digit(n, d) to count occurrences of d from 0 to n.higher = n // (10^{pos+1}) (digits to the left)current = (n // 10^{pos}) % 10 (digit at current position)lower = n % (10^{pos}) (digits to the right)current < d: The digit d appears higher * 10^{pos} times at this position.current == d: It appears higher * 10^{pos} + (lower + 1) times.current > d: It appears (higher + 1) * 10^{pos} times.d == 0: We must not count leading zeros, so we skip the highest position if pos is the most significant digit.count_digit(num2, digit) - count_digit(num1-1, digit) as the answer.
Example: Suppose num1 = 25, num2 = 35, digit = 3.
The optimized algorithm computes this for any range, even for very large numbers, by analyzing digit positions.
Brute-force approach:
num2 - num1 + 1), and D is the number of digits per number (up to 10 for large numbers).num2 (at most 10 for 32-bit integers).
The main insight is to avoid brute-force counting by using digit position analysis. By counting how many times the digit appears in each position across all numbers up to n, we can efficiently solve the problem for any range and any digit, even for very large numbers. This approach leverages mathematical properties of numbers and is a classic example of digit dynamic programming.
def countDigitOccurrences(num1: int, num2: int, digit: int) -> int:
def count_digit(n: int, d: int) -> int:
if n < 0:
return 0
res = 0
str_n = str(n)
length = len(str_n)
for pos in range(length):
power = 10 ** (length - pos - 1)
current_digit = int(str_n[pos])
left = int(str_n[:pos]) if pos > 0 else 0
right = int(str_n[pos+1:]) if pos < length - 1 else 0
if d == 0 and pos == 0:
continue # skip leading zero count
if current_digit < d:
res += left * power
elif current_digit == d:
res += left * power + right + 1
else:
res += (left + 1) * power
return res
return count_digit(num2, digit) - count_digit(num1 - 1, digit)
int count_digit(long long n, int d) {
if (n < 0) return 0;
int res = 0;
string str_n = to_string(n);
int length = str_n.size();
for (int pos = 0; pos < length; ++pos) {
long long power = 1;
for (int i = 0; i < length - pos - 1; ++i) power *= 10;
int current_digit = str_n[pos] - '0';
int left = (pos > 0) ? stoi(str_n.substr(0, pos)) : 0;
int right = (pos < length - 1) ? stoi(str_n.substr(pos + 1)) : 0;
if (d == 0 && pos == 0) continue;
if (current_digit < d) {
res += left * power;
} else if (current_digit == d) {
res += left * power + right + 1;
} else {
res += (left + 1) * power;
}
}
return res;
}
int countDigitOccurrences(int num1, int num2, int digit) {
return count_digit(num2, digit) - count_digit(num1 - 1, digit);
}
public class Solution {
private int countDigit(long n, int d) {
if (n < 0) return 0;
int res = 0;
String str = Long.toString(n);
int length = str.length();
for (int pos = 0; pos < length; ++pos) {
long power = (long)Math.pow(10, length - pos - 1);
int currentDigit = str.charAt(pos) - '0';
int left = (pos > 0) ? Integer.parseInt(str.substring(0, pos)) : 0;
int right = (pos < length - 1) ? Integer.parseInt(str.substring(pos + 1)) : 0;
if (d == 0 && pos == 0) continue;
if (currentDigit < d) {
res += left * power;
} else if (currentDigit == d) {
res += left * power + right + 1;
} else {
res += (left + 1) * power;
}
}
return res;
}
public int countDigitOccurrences(int num1, int num2, int digit) {
return countDigit(num2, digit) - countDigit(num1 - 1, digit);
}
}
function countDigitOccurrences(num1, num2, digit) {
function count_digit(n, d) {
if (n < 0) return 0;
let res = 0;
let str_n = n.toString();
let length = str_n.length;
for (let pos = 0; pos < length; ++pos) {
let power = Math.pow(10, length - pos - 1);
let current_digit = parseInt(str_n[pos]);
let left = pos > 0 ? parseInt(str_n.slice(0, pos)) : 0;
let right = pos < length - 1 ? parseInt(str_n.slice(pos + 1)) : 0;
if (d === 0 && pos === 0) continue;
if (current_digit < d) {
res += left * power;
} else if (current_digit === d) {
res += left * power + right + 1;
} else {
res += (left + 1) * power;
}
}
return res;
}
return count_digit(num2, digit) - count_digit(num1 - 1, digit);
}