Welcome to Subscribe On Youtube
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 <= num2min_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 <= 10221 <= 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$.
-
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; } } -
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; } }; -
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 -
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 } -
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; }