统计整数数目

标签: 数学 字符串 动态规划

难度: Hard

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

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

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

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

示例 1：

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

示例 2：

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

提示：

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

Submission

运行时间: 44 ms

内存: 17.9 MB

class Solution:
    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
        n=len(num2)
        num1=str(int(num1)-1)
        num1='0'*(n-len(num1))+num1
        num1,num2=tuple(map(int,num1)),tuple(map(int,num2))
        MOD=1_000_000_007
        @cache
        def ndn(n,dsum):
            if dsum<0:
                return 0
            if n==0:
                return 1
            res=0
            for cd in range(10):
                res=(res+ndn(n-1,dsum-cd))%MOD
            return res
        def ddn(num,max_sum):
            if max_sum<0:
                return 0
            if len(num)==0:
                return 1
            res=0
            for cd in range(num[0]):
                res=(res+ndn(len(num)-1,max_sum-cd))%MOD
            return (res+ddn(num[1:],max_sum-num[0]))%MOD
        return ((ddn(num2,max_sum)-ddn(num2,min_sum-1))-(ddn(num1,max_sum)-ddn(num1,min_sum-1)))%MOD



@cache
def free_digits(N, limit):
    if limit < 0:
        return 0
    if N == 0:
        return 1
    return sum(free_digits(N - 1, limit - i) for i in range(10)) % 1000000007


class Solution:
    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:

        def total(num, max_sum):
            if max_sum < 0:
                return 0
            if not num:
                return 1
            ans = 0
            for i in range(ord(num[0]) - ord('0')):
                ans += free_digits(len(num) - 1, max_sum - i)
            ans += total(num[1:], max_sum - (ord(num[0]) - ord('0')))
            #print("total", num, max_sum, ans)
            return ans % 1000000007
        num1d = str(int(num1) - 1)
        return ((total(num2, max_sum) - total(num2, min_sum - 1)) - (total(num1d, max_sum) - total(num1d, min_sum - 1))) % 1000000007

Explain

The solution uses a digit dynamic programming approach to efficiently count numbers within a specific range whose digit sum falls between given bounds. It considers two main functions: 1) 'ndn(n, dsum)', which calculates how many n-digit numbers have a digit sum exactly equal to 'dsum'. 2) 'ddn(num, max_sum)', which calculates the count of numbers up to 'num' that have a digit sum of at most 'max_sum'. The main idea is to count the numbers satisfying the conditions up to 'num2' and subtract the count of numbers up to 'num1' - 1 (thus counting numbers between 'num1' and 'num2'), and adjust this for the specified digit sum range.

时间复杂度: O(D^2 * 10 * max_sum) where D is the number of digits in 'num2'. This complexity stems from the iteration over all possible first digits and recursive processing for each subsequent digit.

空间复杂度: O(D * max_sum), which accounts for the maximum depth of recursion multiplied by the range of digit sums cached.

class Solution:
    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
        MOD = 1_000_000_007
        num1 = str(int(num1) - 1) # Convert num1 to one less to include it in range during subtraction
        n = len(num2)
        num1 = '0' * (n - len(num1)) + num1 # Pad num1 to match the length of num2
        num1, num2 = tuple(map(int, num1)), tuple(map(int, num2)) # Convert strings to tuple of digits
        @cache
        def ndn(n, dsum): # Count of n-digit numbers with digit sum exactly 'dsum'
            if dsum < 0: return 0
            if n == 0: return 1 # Base case: one way (the number 0)
            res = 0
            for cd in range(10): # Loop through each digit from 0 to 9
                res = (res + ndn(n-1, dsum-cd)) % MOD
            return res
        def ddn(num, max_sum): # Dynamic digit sum calculation up to 'num'
            if max_sum < 0: return 0
            if not num: return 1 # Base case: one way if no digits left
            res = 0
            for cd in range(num[0]): # Try all digits less than the first digit of num
                res = (res + ndn(len(num)-1, max_sum-cd)) % MOD
            return (res + ddn(num[1:], max_sum-num[0])) % MOD # Include the case where first digit is num[0]
        return ((ddn(num2, max_sum) - ddn(num2, min_sum-1)) - (ddn(num1, max_sum) - ddn(num1, min_sum-1))) % MOD

Explore

在`ndn(n, dsum)`函数中，基本情况是当`n == 0`时返回1。这表示没有更多的数字可以选择，如果此时`dsum`也正好为0，则唯一可能的“数字”是数值0（没有任何数字组成的数）。因此，这里返回1表示存在一种方法（即选择数字0）使得数字总和为0。如果`dsum`不为0，会由函数其他部分返回0，因为无法通过非零数量的数字达到非零的`dsum`。

在`ddn(num, max_sum)`函数中，它首先考虑所有小于给定数字`num`的最高位的可能数字，并使用`ndn`递归计算每种情况的结果。对每个小于最高位的数字，它计算剩下的位数可以形成的所有数字和。这确保了除了最高位的所有其他位的组合都被考虑到。接着，函数递归地考虑最高位数字正好等于`num`的第一个数字的情况，并处理剩余的数字。这种方法确保了从最高位到最低位的每一位都被正确地考虑到，从而可以生成所有小于或等于`num`的数字。

在计算区间`[num1, num2]`内满足条件的数字数量时，需要将`num1`减去1，因为`ddn`函数计算的是小于或等于给定数字的所有可能的数字。如果不减1，那么计算结果会包括`num1`，而我们需要的是从`num1`开始的区间。通过将`num1`减去1并计算到`num1-1`为止的数字，然后从`num2`的结果中减去这个结果，我们可以确保区间是正确的`[num1, num2]`。这种处理确保了在边界的处理上，我们不会错过或多计算任何数字。

在`ddn`函数中，如果`max_sum < 0`，这意味着不可能有任何有效的数字组合其数位和为一个负数。因此，在这种情况下直接返回0是合理的，表示不存在任何数位组合能够满足数位和小于0的条件。这是一个必要的边界条件检查，它阻止了无效计算的进行，并确保递归能在合适的条件下正确终止。