LeetCode 2719 - Count of Integers

LeetCode Problem 2719

Difficulty: 🔴 Hard
Topics: Math, String, Dynamic Programming

Solution

Problem Understanding

The problem asks us to count how many integers lie between two given numeric strings num1 and num2 (inclusive) such that the sum of their digits is between min_sum and max_sum. In other words, we are looking for all integers $x$ where num1 <= x <= num2 and the sum of digits of $x$ falls in the specified range. The result should be returned modulo $10^9 + 7$ due to potentially large output sizes.

The inputs num1 and num2 are strings rather than integers, which suggests that we need to handle numbers that are potentially very large, beyond typical integer limits. min_sum and max_sum define the valid range for the sum of digits.

Important edge cases include numbers where num1 equals num2, the smallest valid range of sums, and cases where numbers contain leading zeros if we attempt manual string manipulation. The problem guarantees that 1 <= num1 <= num2 <= 10^22 and 1 <= min_sum <= max_sum <= 400, so we need an algorithm that efficiently handles very large numbers and large digit sums.

Approaches

The brute-force approach would generate every integer between num1 and num2, compute the digit sum for each, and count those whose sum lies in [min_sum, max_sum]. While correct, this approach is too slow because the range between num1 and num2 can be extremely large (up to $10^{22}$ numbers), making this solution infeasible.

The optimal approach uses digit dynamic programming (digit DP). The key insight is that we can recursively calculate the number of valid numbers by processing one digit at a time, keeping track of the current sum of digits, and whether the number is still bounded by num1 or num2. This approach avoids generating all numbers explicitly. We define a DP state as dp(pos, tightLow, tightHigh, currSum), representing the number of ways to fill digits from position pos such that the number remains within bounds and the current digit sum is currSum.

Algorithm Walkthrough

1. Convert both num1 and num2 to lists of digits to simplify indexing and comparison.
2. Define a recursive function dfs(pos, tightLow, tightHigh, currSum) where pos is the current digit index, tightLow indicates if the current prefix is still constrained by num1, tightHigh indicates if constrained by num2, and currSum is the sum of digits chosen so far.
3. If pos reaches the length of the number, check if currSum is within [min_sum, max_sum]. If yes, return 1; otherwise, return 0.
4. If the current state has been computed before, return the cached result.
5. Determine the lower and upper bounds for the current digit: if constrained by num1 or num2, use the corresponding digit; otherwise, use 0-9.
6. Iterate over all digits in the valid range and recursively call dfs for the next position, updating tightLow, tightHigh, and currSum.
7. Sum all recursive results modulo $10^9 + 7$ and cache them.
8. Return the result from the initial call dfs(0, True, True, 0).

Why it works: The recursive digit DP correctly enumerates all valid numbers without generating them explicitly, ensuring all bounds are respected and sums are within limits. Memoization guarantees that each unique state is computed only once, which ensures efficiency.

Python Solution

class Solution:
    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
        MOD = 10**9 + 7
        digits1 = [int(c) for c in num1]
        digits2 = [int(c) for c in num2]
        n = len(digits2)

        from functools import lru_cache

        @lru_cache(None)
        def dfs(pos: int, tightLow: bool, tightHigh: bool, currSum: int) -> int:
            if pos == n:
                return 1 if min_sum <= currSum <= max_sum else 0

            low = digits1[pos] if tightLow else 0
            high = digits2[pos] if tightHigh else 9
            total = 0

            for d in range(low, high + 1):
                newTightLow = tightLow and (d == digits1[pos])
                newTightHigh = tightHigh and (d == digits2[pos])
                total += dfs(pos + 1, newTightLow, newTightHigh, currSum + d)
                total %= MOD

            return total

        # Pad num1 with leading zeros if necessary
        digits1 = [0] * (n - len(digits1)) + digits1
        return dfs(0, True, True, 0)

Explanation: The Python solution converts num1 and num2 to digit lists. Leading zeros are padded to align lengths. The dfs function recursively counts valid numbers, respecting tight bounds on both ends and keeping track of the current digit sum. Memoization via lru_cache ensures repeated states are computed once. The modulo is applied during summation to handle large numbers.

Go Solution

package main

func count(num1 string, num2 string, min_sum int, max_sum int) int {
    const MOD = 1_000_000_007
    n := len(num2)

    digits1 := make([]int, n)
    digits2 := make([]int, n)

    for i := 0; i < n; i++ {
        digits2[i] = int(num2[i] - '0')
    }

    for i := 0; i < len(num1); i++ {
        digits1[n-len(num1)+i] = int(num1[i] - '0')
    }

    memo := make([][][][]int, n+1)
    for i := range memo {
        memo[i] = make([][][]int, 2)
        for j := range memo[i] {
            memo[i][j] = make([][]int, 2)
            for k := range memo[i][j] {
                memo[i][j][k] = make([]int, max_sum+2)
                for l := range memo[i][j][k] {
                    memo[i][j][k][l] = -1
                }
            }
        }
    }

    var dfs func(pos, tightLow, tightHigh, currSum int) int
    dfs = func(pos, tightLow, tightHigh, currSum int) int {
        if pos == n {
            if currSum >= min_sum && currSum <= max_sum {
                return 1
            }
            return 0
        }

        tl := 0
        if tightLow {
            tl = 1
        }
        th := 0
        if tightHigh {
            th = 1
        }

        if memo[pos][tl][th][currSum] != -1 {
            return memo[pos][tl][th][currSum]
        }

        low := 0
        if tightLow {
            low = digits1[pos]
        }
        high := 9
        if tightHigh {
            high = digits2[pos]
        }

        total := 0
        for d := low; d <= high; d++ {
            newTightLow := tightLow && (d == digits1[pos])
            newTightHigh := tightHigh && (d == digits2[pos])
            total += dfs(pos+1, btoi(newTightLow), btoi(newTightHigh), currSum+d)
            total %= MOD
        }

        memo[pos][tl][th][currSum] = total
        return total
    }

    return dfs(0, 1, 1, 0)
}

func btoi(b bool) int {
    if b {
        return 1
    }
    return 0
}

Go-specific notes: Go does not have lru_cache, so a 4D memoization slice is explicitly created. Boolean flags are converted to integers for indexing. Leading zeros are handled by aligning digits1 with digits2. The modulo operation ensures integer overflow is avoided.

Worked Examples

Example 1: num1 = "1", num2 = "12", min_sum = 1, max_sum = 8