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 [minsum,..maxsum]. 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 posth 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 [minsum,..maxsum]. If it is, return 1, otherwise return 0.
The time complexity is O(10 × n × maxsum), and the space complexity is O(n × maxsum). Here, n represents the length of num.
Similar problems:
PythonJavaC++GoTypeScript
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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
