Hard

Count of Integers

LAB

Return how many integers in [num1,num2] have digit sum between minSum and maxSum, modulo 1000000007.

EXAMPLES

Example 1

Input
{
  "num1": "1",
  "num2": "12",
  "minSum": 1,
  "maxSum": 8
}

Output
11

FUNCTION SHAPE

num1: stringnum2: stringminSum: intmaxSum: int→int

SOLUTION NOTE

Track running digit sum. At the end, check if sum is in valid range. No need for leading zero tracking here.

Reveal reference solution +

pythonREFERENCE

def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
    MOD = 10**9 + 7

    def count_up_to(s):
        @cache
        def dp(i, digit_sum, tight):
            if i == len(s):
                return 1 if min_sum <= digit_sum <= max_sum else 0
            max_d = int(s[i]) if tight else 9
            res = 0
            for d in range(max_d + 1):
                next_tight = tight and d == max_d
                res = (res + dp(i+1, digit_sum + d, next_tight)) % MOD
            return res
        return dp(0, 0, True)

    return (count_up_to(num2) - count_up_to(str(int(num1) - 1))) % MOD

TimeO(digits × max_sum)

SpaceO(digits × max_sum)

Open on LeetCode ↗