Count of Integers — Solution in Python, Java & C++
Count of Integers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Count of Integers is a hard coding problem on strings, dynamic programming and math, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Strings, Dynamic Programming, Math, Digit DP
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two numeric strings num1 and num2 and two integers min_sum and max_sum. An integer x is good when:
num1 <= x <= num2, andmin_sum <= digit_sum(x) <= max_sum,
where digit_sum(x) is the sum of the decimal digits of x. Return the number of good integers. Since it can be huge, return it modulo 10^9 + 7.
Example 1
Input: num1 = "1", num2 = "12", min_sum = 1, max_sum = 8
Output: 11
Explanation: 1, 2, 3, 4, 5, 6, 7, 8, 10, 11 and 12 qualify.
Example 2
Input: num1 = "1", num2 = "5", min_sum = 1, max_sum = 5
Output: 5
Explanation: 1, 2, 3, 4 and 5.
Example 3
Input: num1 = "100", num2 = "199", min_sum = 20, max_sum = 400
Output: 0
Explanation: The largest digit sum in range is 1 + 9 + 9 = 19.
Constraints
1 <= num1 <= num2 <= 10^221 <= min_sum <= max_sum <= 400num1 and num2 have no leading zeros
Hints for Count of Integers
Hint 1
Counting a range is the difference of two prefix counts:
good(num2) - good(num1) + [num1 is good], wheregood(X)counts integers in[0, X].Hint 2
To count integers up to
Xwith a given digit sum, build them digit by digit: once a digit is smaller thanX's digit at that position, every later digit is free. That is digit DP over (position, digit sum so far, still tight?).Hint 3
The digit sum never exceeds
9 × 22 = 198, so the state space is tiny. Keep the counts modulo10^9 + 7and fix up a negative difference at the end.
How to solve Count of Integers
Turn the range into two prefix counts and count each prefix with a digit DP that tracks the running digit sum, splitting off the 'already smaller than X' numbers from the single 'equal to X so far' prefix.
Approach
- Define
good(X)= number of integers0 <= y <= Xwithmin_sum <= digit_sum(y) <= max_sum. - Scan
X's digits left to right. Keepfree[s]= how many prefixes are already smaller thanX's prefix with digit sums(leading zeros allowed — they add nothing), plus the sumtofX's own prefix. - At each digit
d: everyfree[s]extends with any digit0..9; the tight prefix extends with digits0..d-1intofree; thent += d. - At the end
good(X)= Σfree[s]oversin range, plus 1 iftitself is in range (the numberX). - Answer:
good(num2) - good(num1) + [digit_sum(num1) in range], taken modulo10^9 + 7.
Why it works
Every integer below X (padded with leading zeros to the same length) has a unique first position where it drops below X; at that point it enters free exactly once, and the free extensions enumerate all of its continuations. So each y < X is counted once with its digit sum, and X itself is handled separately.
Complexity
- Time —
O(L · S · 10) for L ≤ 23 digits and S ≤ 199 reachable sums - Space —
O(S)
Pitfalls
num1andnum2exceed 64-bit integers — never convert them to numbers.good(num2) - good(num1)excludesnum1itself; add it back when its digit sum qualifies.- The modular difference can be negative; add the modulus before the final reduction.
Reference solution
Python
MOD = 10 ** 9 + 7
def countIntegers(num1: str, num2: str, min_sum: int, max_sum: int) -> int:
hi = min(max_sum, 9 * len(num2))
if min_sum > hi:
return 0
inside = 1 if min_sum <= sum(ord(c) - 48 for c in num1) <= max_sum else 0
return (_good(num2, min_sum, hi) - _good(num1, min_sum, hi) + inside) % MOD
def _good(x: str, lo: int, hi: int) -> int:
free = [0] * (hi + 1)
tight = 0
for ch in x:
d = ord(ch) - 48
nf = [0] * (hi + 1)
for s in range(hi + 1):
nf[s] = sum(free[max(0, s - 9):s + 1]) % MOD
for k in range(d):
if tight + k <= hi:
nf[tight + k] += 1
tight += d
free = nf
total = sum(free[lo:hi + 1])
if lo <= tight <= hi:
total += 1
return total % MODJava
static final long CNT_MOD = 1000000007L;
static long countGood(String x, int lo, int hi) {
long[] free = new long[hi + 1];
int tight = 0;
for (int p = 0; p < x.length(); p++) {
int d = x.charAt(p) - '0';
long[] nf = new long[hi + 1];
long win = 0;
for (int s = 0; s <= hi; s++) {
win += free[s];
if (s >= 10) win -= free[s - 10];
win = ((win % CNT_MOD) + CNT_MOD) % CNT_MOD;
nf[s] = win;
}
for (int k = 0; k < d; k++) if (tight + k <= hi) nf[tight + k] = (nf[tight + k] + 1) % CNT_MOD;
tight += d;
free = nf;
}
long total = 0;
for (int s = lo; s <= hi; s++) total = (total + free[s]) % CNT_MOD;
if (tight >= lo && tight <= hi) total = (total + 1) % CNT_MOD;
return total;
}
public static int countIntegers(String num1, String num2, int min_sum, int max_sum) {
int hi = Math.min(max_sum, 9 * num2.length());
if (min_sum > hi) return 0;
int ds = 0;
for (int i = 0; i < num1.length(); i++) ds += num1.charAt(i) - '0';
long inside = (ds >= min_sum && ds <= max_sum) ? 1 : 0;
long ans = (countGood(num2, min_sum, hi) - countGood(num1, min_sum, hi) + inside) % CNT_MOD;
return (int) ((ans + CNT_MOD) % CNT_MOD);
}C++
static long long countGood(const string& x, int lo, int hi) {
const long long MOD = 1000000007LL;
vector<long long> freeCnt(hi + 1, 0);
int tight = 0;
for (char ch : x) {
int d = ch - '0';
vector<long long> nf(hi + 1, 0);
long long win = 0;
for (int s = 0; s <= hi; s++) {
win += freeCnt[s];
if (s >= 10) win -= freeCnt[s - 10];
win = ((win % MOD) + MOD) % MOD;
nf[s] = win;
}
for (int k = 0; k < d; k++) if (tight + k <= hi) nf[tight + k] = (nf[tight + k] + 1) % MOD;
tight += d;
freeCnt = nf;
}
long long total = 0;
for (int s = lo; s <= hi; s++) total = (total + freeCnt[s]) % MOD;
if (tight >= lo && tight <= hi) total = (total + 1) % MOD;
return total;
}
int countIntegers(string num1, string num2, int min_sum, int max_sum) {
const long long MOD = 1000000007LL;
int hi = min(max_sum, 9 * (int)num2.size());
if (min_sum > hi) return 0;
int ds = 0;
for (char ch : num1) ds += ch - '0';
long long inside = (ds >= min_sum && ds <= max_sum) ? 1 : 0;
long long ans = (countGood(num2, min_sum, hi) - countGood(num1, min_sum, hi) + inside) % MOD;
return (int)((ans + MOD) % MOD);
}JavaScript
var countIntegers = function(num1, num2, min_sum, max_sum) {
var MOD = 1000000007;
var hi = Math.min(max_sum, 9 * num2.length);
if (min_sum > hi) return 0;
var good = function(x) {
var free = new Array(hi + 1).fill(0), tight = 0;
for (var p = 0; p < x.length; p++) {
var d = x.charCodeAt(p) - 48, nf = new Array(hi + 1).fill(0), win = 0;
for (var s = 0; s <= hi; s++) {
win += free[s];
if (s - 10 >= 0) win -= free[s - 10];
win %= MOD;
if (win < 0) win += MOD;
nf[s] = win;
}
for (var k = 0; k < d; k++) if (tight + k <= hi) nf[tight + k] = (nf[tight + k] + 1) % MOD;
tight += d;
free = nf;
}
var total = 0;
for (var s = min_sum; s <= hi; s++) total = (total + free[s]) % MOD;
if (tight >= min_sum && tight <= hi) total = (total + 1) % MOD;
return total;
};
var ds = 0;
for (var i = 0; i < num1.length; i++) ds += num1.charCodeAt(i) - 48;
var inside = ds >= min_sum && ds <= max_sum ? 1 : 0;
return ((good(num2) - good(num1) + inside) % MOD + MOD) % MOD;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming