Count of Integers

Hard
1635.

Count of Integers

Count of Integers is a hard coding problem on strings, dynamic programming and math, asked in Amazon and Google interviews.

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, and
  • min_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^22
  • 1 <= min_sum <= max_sum <= 400
  • num1 and num2 have no leading zeros
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} num1
 * @param {string} num2
 * @param {number} min_sum
 * @param {number} max_sum
 * @return {number}
 */
var countIntegers = function(num1, num2, min_sum, max_sum) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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, and
  • min_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^22
  • 1 <= min_sum <= max_sum <= 400
  • num1 and num2 have no leading zeros

Hints for Count of Integers

  1. Hint 1

    Counting a range is the difference of two prefix counts: good(num2) - good(num1) + [num1 is good], where good(X) counts integers in [0, X].

  2. Hint 2

    To count integers up to X with a given digit sum, build them digit by digit: once a digit is smaller than X's digit at that position, every later digit is free. That is digit DP over (position, digit sum so far, still tight?).

  3. Hint 3

    The digit sum never exceeds 9 × 22 = 198, so the state space is tiny. Keep the counts modulo 10^9 + 7 and 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

  1. Define good(X) = number of integers 0 <= y <= X with min_sum <= digit_sum(y) <= max_sum.
  2. Scan X's digits left to right. Keep free[s] = how many prefixes are already smaller than X's prefix with digit sum s (leading zeros allowed — they add nothing), plus the sum t of X's own prefix.
  3. At each digit d: every free[s] extends with any digit 0..9; the tight prefix extends with digits 0..d-1 into free; then t += d.
  4. At the end good(X) = Σ free[s] over s in range, plus 1 if t itself is in range (the number X).
  5. Answer: good(num2) - good(num1) + [digit_sum(num1) in range], taken modulo 10^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

  • num1 and num2 exceed 64-bit integers — never convert them to numbers.
  • good(num2) - good(num1) excludes num1 itself; 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 % MOD

Java

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