What is the key dynamic programming pattern used in the Count of Integers problem?

The problem leverages state transition dynamic programming to count numbers within a given range that satisfy the digit sum constraints.

How do I optimize the Count of Integers solution to handle large inputs?

By applying dynamic programming with state transitions over the digits of num1 and num2, and using modulo 10^9 + 7 to manage large results.

What is the time complexity of the Count of Integers problem?

The time complexity is generally O(d * range), where d is the number of digits in the largest number and range is the difference between num1 and num2.

How does GhostInterview help with the Count of Integers problem?

GhostInterview provides targeted assistance with the state transition approach and helps ensure correctness with dynamic programming techniques for counting valid numbers.

What are some common pitfalls when solving the Count of Integers problem?

Common pitfalls include failing to optimize with dynamic programming, incorrect digit sum calculations, and neglecting to apply modulo 10^9 + 7 correctly.

#2719

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

统计整数数目

给你两个数字字符串 num1 和 num2 ，以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件，我们称它是一个好整数： num1 min_sum . 请你返回好整数的数目。答案可能很大，请返回答案对 10 9 + 7 取余后的结果。注意， digit_sum(x)…

数学字符串动态规划

题目描述

给你两个数字字符串 num1 和 num2 ，以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件，我们称它是一个好整数：

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

请你返回好整数的数目。答案可能很大，请返回答案对 10⁹ + 7 取余后的结果。

注意，digit_sum(x) 表示 x 各位数字之和。

示例 1：

输入：num1 = "1", num2 = "12", min_sum = 1, max_sum = 8
输出：11
解释：总共有 11 个整数的数位和在 1 到 8 之间，分别是 1,2,3,4,5,6,7,8,10,11 和 12 。所以我们返回 11 。

示例 2：

输入：num1 = "1", num2 = "5", min_sum = 1, max_sum = 5
输出：5
解释：数位和在 1 到 5 之间的 5 个整数分别为 1,2,3,4 和 5 。所以我们返回 5 。

提示：

1 <= num1 <= num2 <= 10²²
1 <= min_sum <= max_sum <= 400

lightbulb

解题思路

方法一：数位 DP

题目实际上求的是区间 $[num1,..num2]$ 中，数位和在 $[min\_sum,..max\_sum]$ 的数的个数。对于这种区间 $[l,..r]$ 的问题，我们可以考虑转化为求 $[1,..r]$ 和 $[1,..l-1]$ 的答案，然后相减即可。

对于 $[1,..r]$ 的答案，我们可以使用数位 DP 来求解。我们设计一个函数 $dfs(pos, s, limit)$ 表示当前处理到第 $pos$ 位，数位和为 $s$ ，当前数是否有上界限制 $limit$ 的方案数。其中 $pos$ 从高到低枚举。

对于 $dfs(pos, s, limit)$ ，我们可以枚举当前数位 $i$ 的值，然后递归计算 $dfs(pos+1, s+i, limit \bigcap i==up)$ ，其中 $up$ 表示当前数位的上界。如果 $limit$ 为真，那么 $up$ 就是当前数位的上界，否则 $up$ 为 $9$ 。如果 $pos$ 大于等于 $num$ 的长度，那么我们就可以判断 $s$ 是否在 $[min\_sum,..max\_sum]$ 的范围内，如果在就返回 $1$ ，否则返回 $0$ 。

时间复杂度 $O(10 \times n \times max\_sum)$ ，空间复杂度 $O(n \times max\_sum)$ 。其中 $n$ 表示 $num$ 的长度。

相似题目：

2801. 统计范围内的步进数字数目

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate's ability to define and implement dynamic programming states is crucial.
question_mark
Look for a strong understanding of digit-based state transitions.
question_mark
Ensure the candidate handles large numbers correctly using modulo operations.

warning

常见陷阱

外企场景

error
Not optimizing the solution using dynamic programming, leading to a time complexity that is too high.
error
Incorrectly calculating the sum of digits or failing to properly track the transition states between digits.
error
Failing to apply modulo 10^9 + 7 correctly, potentially causing overflow or incorrect results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Variant where the sum of digits can only be calculated for specific subranges of num1 and num2.
arrow_right_alt
Variant where num1 and num2 are very large strings, requiring optimizations beyond basic dynamic programming.
arrow_right_alt
Variant with additional constraints on the maximum sum of digits, which would require more advanced state transitions.

help

常见问题

外企场景

继续练习

#2851 字符串转换 #2999 统计强大整数的数目 #2266 统计打字方案数