2719. Count of Integers

Problem Link

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

Solution

---

Python3

class Solution:
    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
        M = 10 ** 9 + 7
 
        num1 = list(map(int, str(int(num1) - 1)))
        num2 = list(map(int, num2))
        
        def helper(digits):
            N = len(digits)
 
            @cache
            def go(index, tight, ssum):
                if index == N:
                    return min_sum <= ssum <= max_sum
                
                limit = digits[index] if tight else 9
                
                res = 0
                
                for digit in range(limit + 1):
                    nxtTight = tight and digit == digits[index]
                    
                    res += go(index + 1, nxtTight, ssum + digit)
                    res %= M
                
                return res
            
            return go(0, True, 0)
        
        a = helper(num2)
        b = helper(num1)
        
        return (a - b) % M