LeetCode Solutions Blog

Count of Integers

Number: 2757

Difficulty: Hard

Paid? No

Problem Description

Given two numeric strings num1 and num2 and two integers min_sum and max_sum, count how many integers x in the range [num1, num2] have a digit sum between min_sum and max_sum (inclusive). Return the count modulo 10^9+7.

Key Insights

The integer range is huge (up to 10^22), so iterating through each number is infeasible.
Use digit dynamic programming (DP) to count numbers whose digit sum satisfies certain thresholds.
Count the numbers less than or equal to a given bound that have a digit sum ≤ a limit.
The final answer can be obtained by computing the count for the upper bound and the count for (lower bound - 1), and then taking the difference.
To count numbers with digit sum in [min_sum, max_sum], compute:
- count(max_sum) - count(min_sum - 1)
DP states include: the current digit index, the current sum, and a tight flag indicating whether the prefix is the same as the bound.

Space and Time Complexity

Time Complexity: O(digits * max_sum * 2)
• There are at most 22 digits and the DP state runs over sum values from 0 to max_sum (up to 400) with 2 tight states.
Space Complexity: O(digits * max_sum * 2) for memoization storage.

Solution

We solve the problem using a digit DP approach. The general idea is to build a recursive function that, given a prefix of the number, returns the count of ways to form numbers that do not exceed the given bound and have a digit sum below or equal to a particular target.
Steps include:

Convert the bound string into a list of digits.
Define a recursive DP function with parameters: the current index in the digit list, the cumulative digit sum so far, and a flag (tight) to indicate whether the number we are constructing is still equal to the prefix of the given bound.
If we have processed all digits, return a count (1 if the accumulated sum is within the target, else 0).
For each digit position, iterate through all possible choices that do not violate the bound if the tight flag is set.
Cache overlapping states to optimize the recursive calls.
Compute the answer for both the upper bound (num2) and for (num1 - 1) and subtract to get the final result for the range.
Handle modulo arithmetic appropriately.

Code Solutions

# Python Solution

MOD = 10**9 + 7

def countNumbers(num, target):
    # Convert the number into a list of digits
    digits = list(map(int, list(num)))
    n = len(digits)
    
    from functools import lru_cache
    @lru_cache(maxsize=None)
    def dp(index, curr_sum, tight):
        # If current digit sum exceeds target, no valid number can be formed
        if curr_sum > target:
            return 0
        # Base case: if we have processed all digits,
        # count this number if the digit sum is within target
        if index == n:
            return 1
        res = 0
        # Upper limit for current digit based on tight flag
        end = digits[index] if tight else 9
        for d in range(0, end + 1):
            # Determine if the next state will remain tight.
            nextTight = tight and (d == end)
            res = (res + dp(index + 1, curr_sum + d, nextTight)) % MOD
        return res

    return dp(0, 0, True)

def countGoodIntegers(num, target_low, target_high):
    # Count numbers <= num with digit sum <= some target
    return countNumbers(num, target_high)

def countInRange(num1, num2, min_sum, max_sum):
    # Count numbers with digit sum <= max_sum
    countUpToNum2_max = countNumbers(num2, max_sum)
    # Count numbers with digit sum <= (min_sum - 1)
    # For subtracting lower part, we adjust num1 by decrementing it
    # Decrement function for string number
    def dec(num_str):
        num_list = list(num_str)
        i = len(num_list) - 1
        while i >= 0:
            if num_list[i] != '0':
                num_list[i] = str(int(num_list[i]) - 1)
                break
            else:
                num_list[i] = '9'
                i -= 1
        # Remove leading zeros if any
        res = ''.join(num_list).lstrip('0')
        return res if res != "" else "0"
    
    num1_minus = dec(num1)
    countUpToBeforeNum1_min = countNumbers(num1_minus, min_sum - 1) if num1_minus != "0" else 0
    countUpToBeforeNum1_max = countNumbers(num1_minus, max_sum) if num1_minus != "0" else 0
    countBeforeNum1 = (countUpToBeforeNum1_max - countUpToBeforeNum1_min) % MOD

    # Calculate the count in [num1, num2] for numbers with digit sum in [min_sum, max_sum]
    countNum2Range = (countUpToNum2_max - countNumbers(num2, min_sum - 1)) % MOD
    return (countNum2Range - countBeforeNum1) % MOD

# Main function to get the answer
def count_good_integers(num1, num2, min_sum, max_sum):
    # Count for numbers <= num2 with digit sum in range [min_sum, max_sum]
    count_upper = (countNumbers(num2, max_sum) - countNumbers(num2, min_sum - 1)) % MOD
    # Count for numbers <= (num1 - 1) with digit sum in range [min_sum, max_sum]
    def dec(num_str):
        num_list = list(num_str)
        i = len(num_list) - 1
        while i >= 0:
            if num_list[i] != '0':
                num_list[i] = str(int(num_list[i]) - 1)
                break
            else:
                num_list[i] = '9'
                i -= 1
        res = ''.join(num_list).lstrip('0')
        return res if res != "" else "0"
    num1_minus = dec(num1)
    count_lower = 0
    if num1_minus != "0":
        count_lower = (countNumbers(num1_minus, max_sum) - countNumbers(num1_minus, min_sum - 1)) % MOD
    # Final answer for the range [num1, num2]
    return (count_upper - count_lower) % MOD

# Example usage:
print(count_good_integers("1", "12", 1, 8))  # Expected output: 11
print(count_good_integers("1", "5", 1, 5))    # Expected output: 5