Skip to content

2719. Count of Integers

Description

You are given two numeric strings num1 and num2 and two integers max_sum and min_sum. We denote an integer x to be good if:

  • num1 <= x <= num2
  • min_sum <= digit_sum(x) <= max_sum.

Return the number of good integers. Since the answer may be large, return it modulo 109 + 7.

Note that digit_sum(x) denotes the sum of the digits of x.

 

Example 1:

Input: num1 = "1", num2 = "12", min_sum = 1, max_sum = 8
Output: 11
Explanation: There are 11 integers whose sum of digits lies between 1 and 8 are 1,2,3,4,5,6,7,8,10,11, and 12. Thus, we return 11.

Example 2:

Input: num1 = "1", num2 = "5", min_sum = 1, max_sum = 5
Output: 5
Explanation: The 5 integers whose sum of digits lies between 1 and 5 are 1,2,3,4, and 5. Thus, we return 5.

 

Constraints:

  • 1 <= num1 <= num2 <= 1022
  • 1 <= min_sum <= max_sum <= 400

Solutions

Solution 1: Digit DP

The problem is actually asking for the number of integers in the range \([num1,..num2]\) whose digit sum is in the range \([min\_sum,..max\_sum]\). For this kind of range \([l,..r]\) problem, we can consider transforming it into finding the answers for \([1,..r]\) and \([1,..l-1]\), and then subtracting the latter from the former.

For the answer to \([1,..r]\), we can use digit DP to solve it. We design a function \(dfs(pos, s, limit)\), which represents the number of schemes when we are currently processing the \(pos\)th digit, the digit sum is \(s\), and whether the current number has an upper limit \(limit\). Here, \(pos\) is enumerated from high to low.

For \(dfs(pos, s, limit)\), we can enumerate the value of the current digit \(i\), and then recursively calculate \(dfs(pos+1, s+i, limit \bigcap i==up)\), where \(up\) represents the upper limit of the current digit. If \(limit\) is true, then \(up\) is the upper limit of the current digit, otherwise \(up\) is \(9\). If \(pos\) is greater than or equal to the length of \(num\), then we can judge whether \(s\) is in the range \([min\_sum,..max\_sum]\). If it is, return \(1\), otherwise return \(0\).

The time complexity is \(O(10 \times n \times max\_sum)\), and the space complexity is \(O(n \times max\_sum)\). Here, \(n\) represents the length of \(num\).

Similar problems:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
        @cache
        def dfs(pos: int, s: int, limit: bool) -> int:
            if pos >= len(num):
                return int(min_sum <= s <= max_sum)
            up = int(num[pos]) if limit else 9
            return (
                sum(dfs(pos + 1, s + i, limit and i == up) for i in range(up + 1)) % mod
            )

        mod = 10**9 + 7
        num = num2
        a = dfs(0, 0, True)
        dfs.cache_clear()
        num = str(int(num1) - 1)
        b = dfs(0, 0, True)
        return (a - b) % mod

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.math.BigInteger;

class Solution {
    private final int mod = (int) 1e9 + 7;
    private Integer[][] f;
    private String num;
    private int min;
    private int max;

    public int count(String num1, String num2, int min_sum, int max_sum) {
        min = min_sum;
        max = max_sum;
        num = num2;
        f = new Integer[23][220];
        int a = dfs(0, 0, true);
        num = new BigInteger(num1).subtract(BigInteger.ONE).toString();
        f = new Integer[23][220];
        int b = dfs(0, 0, true);
        return (a - b + mod) % mod;
    }

    private int dfs(int pos, int s, boolean limit) {
        if (pos >= num.length()) {
            return s >= min && s <= max ? 1 : 0;
        }
        if (!limit && f[pos][s] != null) {
            return f[pos][s];
        }
        int ans = 0;
        int up = limit ? num.charAt(pos) - '0' : 9;
        for (int i = 0; i <= up; ++i) {
            ans = (ans + dfs(pos + 1, s + i, limit && i == up)) % mod;
        }
        if (!limit) {
            f[pos][s] = ans;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    int count(string num1, string num2, int min_sum, int max_sum) {
        const int mod = 1e9 + 7;
        int f[23][220];
        memset(f, -1, sizeof(f));
        string num = num2;

        function<int(int, int, bool)> dfs = [&](int pos, int s, bool limit) -> int {
            if (pos >= num.size()) {
                return s >= min_sum && s <= max_sum ? 1 : 0;
            }
            if (!limit && f[pos][s] != -1) {
                return f[pos][s];
            }
            int up = limit ? num[pos] - '0' : 9;
            int ans = 0;
            for (int i = 0; i <= up; ++i) {
                ans += dfs(pos + 1, s + i, limit && i == up);
                ans %= mod;
            }
            if (!limit) {
                f[pos][s] = ans;
            }
            return ans;
        };

        int a = dfs(0, 0, true);
        for (int i = num1.size() - 1; ~i; --i) {
            if (num1[i] == '0') {
                num1[i] = '9';
            } else {
                num1[i] -= 1;
                break;
            }
        }
        num = num1;
        memset(f, -1, sizeof(f));
        int b = dfs(0, 0, true);
        return (a - b + mod) % mod;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
func count(num1 string, num2 string, min_sum int, max_sum int) int {
    const mod = 1e9 + 7
    f := [23][220]int{}
    for i := range f {
        for j := range f[i] {
            f[i][j] = -1
        }
    }
    num := num2
    var dfs func(int, int, bool) int
    dfs = func(pos, s int, limit bool) int {
        if pos >= len(num) {
            if s >= min_sum && s <= max_sum {
                return 1
            }
            return 0
        }
        if !limit && f[pos][s] != -1 {
            return f[pos][s]
        }
        var ans int
        up := 9
        if limit {
            up = int(num[pos] - '0')
        }
        for i := 0; i <= up; i++ {
            ans = (ans + dfs(pos+1, s+i, limit && i == up)) % mod
        }
        if !limit {
            f[pos][s] = ans
        }
        return ans
    }
    a := dfs(0, 0, true)
    t := []byte(num1)
    for i := len(t) - 1; i >= 0; i-- {
        if t[i] != '0' {
            t[i]--
            break
        }
        t[i] = '9'
    }
    num = string(t)
    f = [23][220]int{}
    for i := range f {
        for j := range f[i] {
            f[i][j] = -1
        }
    }
    b := dfs(0, 0, true)
    return (a - b + mod) % mod
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function count(num1: string, num2: string, min_sum: number, max_sum: number): number {
    const mod = 1e9 + 7;
    const f: number[][] = Array.from({ length: 23 }, () => Array(220).fill(-1));
    let num = num2;
    const dfs = (pos: number, s: number, limit: boolean): number => {
        if (pos >= num.length) {
            return s >= min_sum && s <= max_sum ? 1 : 0;
        }
        if (!limit && f[pos][s] !== -1) {
            return f[pos][s];
        }
        let ans = 0;
        const up = limit ? +num[pos] : 9;
        for (let i = 0; i <= up; i++) {
            ans = (ans + dfs(pos + 1, s + i, limit && i === up)) % mod;
        }
        if (!limit) {
            f[pos][s] = ans;
        }
        return ans;
    };
    const a = dfs(0, 0, true);
    num = (BigInt(num1) - 1n).toString();
    f.forEach(v => v.fill(-1));
    const b = dfs(0, 0, true);
    return (a - b + mod) % mod;
}

Comments