2719. Count of Integers

Problem Description

The problem involves finding the count of "good" integers within two given numeric string ranges num1 and num2 and a sum range defined by the integers max_sum and min_sum. An integer x is considered "good" if it satisfies two conditions:

It falls between the range num1 and num2, inclusive. For example, if num1 = "12" and num2 = "345", a good integer x could be any number from 12 up to 345.
The digit sum of x (the sum of all its digits) is between the range min_sum and max_sum, inclusive. For instance, with min_sum = 2 and max_sum = 10, a number like 14 with digit sum 1 + 4 = 5 would be considered good.

The computation should return the number of such good integers, and because the result can be very large, it needs to be returned modulo 10^9 + 7.

Intuition

The problem requires a solution that can handle large ranges, making a brute force approach of checking every integer between num1 and num2 impractical, especially when both numbers are large.

The intuition behind the proposed solution is to use depth-first search (DFS) to generate the integers and cumulatively calculate their digit sums. To do this efficiently, we use two core ideas:

Digit Dynamic Programming (DP): We may observe that the digit sum and the formation of numbers can be handled digit by digit from left to right. DP helps keep track of partial results and avoids recalculating them. For instance, if we reach a partial number 12 with a digit sum of 3, we can store this information and use it if we encounter the same partial number again.
Pruning: The search can be split into different cases based on whether the current number is restricted by the upper limit (num2). When generating digits for the current position, if our result is not bound by num2, we are free to use any digit from 0 to 9. If it is bound, we can only use digits up to the corresponding digit in num2.

The variable limit indicates whether the current position is bound by the limit (num2).

The solution also uses memoization (@cache decorator) to optimize and prevent recomputations of states in the DFS—a common enhancement for this type of digit DP problem.

Approach

In our DFS function, we have the parameters pos (the current digit position), s (the current digit sum), and limit (whether we are limited by the upper bound).

If we have reached beyond the last position and the sum s is good, we return 1; otherwise 0.
If we are still building the number, we calculate the upper limit for our current digit (defined by num2 if limit is True, or 9 otherwise).
We iterate through all possible digit choices for the current position and make recursive calls to extend the number and update the sum accordingly.

Finally, we calculate the count for num2, then subtract the count for num1 - 1 because we want the range [num1, num2].

By subtracting the DFS result for num1 - 1 from the result for num2, we ensure that all numbers that fall below num1 are excluded from our final count.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The solution to the problem uses a few sophisticated concepts in algorithm design and implementation, including dynamic programming (DP), memoization, and depth-first search (DFS):

Depth-First Search (DFS): DFS is a recursive method to traverse through possible solutions, in this case, digits of a number from the most to the least significant digit. For every digit of the number being formed, all possible choices between 0 and 9 are explored (or up to the limit set by num2).
Dynamic Programming (DP): Since the problem involves overlapping subproblems (calculating good numbers that start with the same prefixes), DP is used to store solutions to these subproblems so that when they reoccur, we can use the stored solution instead of recomputing it. Thus, DP ensures that each subproblem is solved only once, saving time.
Memoization: Implemented using Python's @cache decorator, memoization is a way of storing the results of expensive function calls and returning the cached result when the same inputs occur again. It is a common technique to optimize recursion in DP.
Pruning: In DFS, recursion can lead to exploring paths that do not contribute to the solution. Pruning is a technique to stop recursion along a path as soon as it's determined that this path cannot possibly lead to a valid solution. The limit boolean variable is used to decide whether we are in a position that is less than the upper limit (num2) and thus can explore all digits up to 9, or if we should restrict the digits to those in num2.

Implementation Walkthrough

The dfs function is defined inside the count method since it operates on different versions of num which is stored in a closure.
dfs takes the current position (pos), the running sum of digits (s), and a boolean limit indicating whether the current path is limited by num2.
Base Case: If the pos advances past the last digit, it checks if s is a good sum (within min_sum and max_sum), returning 1 or 0 as appropriate.
Recursive Case: If not at the end of the number, it considers all digits up to the current digit of num2 (if limit is True) or 9 (if limit is False). For each digit i, dfs is called for the next position with the updated sum and the limit condition updated (it remains True only if i matches the current digit of num2).
Modulo Operation: The sum of the results from dfs for different digits at the current position is taken modulo 10**9 + 7 to keep the intermediate values within the limit set by the problem.

To find the number of good integers between num1 and num2:

dfs is called with num set to num2, the result stored in ans.
The cache is cleared to reset the memoization table.
dfs is called again with num set to one less than num1 (bothering string and int representations).
The result of the second dfs call is subtracted from ans to get the count of the good integers that are at least num1.
The return value is ans % mod, to ensure the output is within the 10**9 + 7 constraint.

This implementation is efficient because the memoization table significantly reduces the computational redundancy that would otherwise occur in a pure recursive solution.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a simple example. Suppose we have:

num1 = "13"
num2 = "21"
min_sum = 3
max_sum = 5

We need to count the "good" integers within the string ranges num1 and num2, and where the digit sum falls between the sum range specified by min_sum and max_sum.

We'll follow the approach outlined in the content:

We initialize DFS with parameters: pos for the current digit position, s for the current sum of the integers, and limit to tell if the current number should be bounded by num2.
Apply DFS to get the count of good integers up to num2 inclusive.
Apply DFS again to get the count of good integers just before num1 (non-inclusive).
Subtract the two counts to find our answer.
The result is taken modulo 10^9 + 7.

Here's a step-by-step for our example:

DFS is called with num2 which is 21. We count all good integers up to this point.
We start at position 0 (digit 2 in num2), with a sum of 0 and limit = True.
- The first digit can only be 1 or 2, as 3 would exceed num2.
For each possible first digit, we recursively call DFS for the next position.
At position 1 (when first digit was 1), we have 0 <= next digit <= 9 because limit = False (1 is less than 2).
- We check all digits for this position with the first digit fixed to 1. There are 9 possible sequences: 10, 11, 12, 13, 14, 15, 16, 17, 18, 19. However, only 13, 14 are "good" since their sums (4 and 5 respectively) are within [min_sum, max_sum].
At position 1 (when the first digit was 2), now limit = True. We must stay within num2 and can now only select the digit 0 or 1.
- We create sequences 20 and 21, with digit sums of 2 and 3 respectively. Only 21 is "good" as it satisfies our sum constraint.

We have found 3 good integers: 13, 14, and 21.

After this, we need to count the number of good integers before num1 (13) and subtract it. This would be any "good" number less than 13, which in this case there are none, since the lowest "good" sum achievable with two digits is 1 + 0 = 1, which doesn’t meet our min_sum = 3.

We now get the final answer:

Good integers up to num2: 3
Good integers before num1: 0
Final count: 3 - 0 = 3 good integers between num1 and num2 with a digit sum between min_sum and max_sum.

Solution Implementation

1from functools import lru_cache
2
3class Solution:
4    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
5        # Define mod constant to avoid repeated calculations
6        mod = 10**9 + 7
7
8        # This function will compute the count using dynamic programming and memoization
9        @lru_cache(None)
10        def dfs(position: int, current_sum: int, is_limit: bool) -> int:
11            # Base case: if we've considered all digits,
12            # check if the sum is within the given range.
13            if position >= len(current_num):
14                return 1 if min_sum <= current_sum <= max_sum else 0
15
16            # Determine the maximum possible digit we can place at this position
17            upper_bound = int(current_num[position]) if is_limit else 9
18          
19            # Recursive step: try all possible digits up to the upper bound 
20            # and count valid numbers
21            count_valid_numbers = sum(
22                dfs(position + 1, current_sum + digit, is_limit and digit == upper_bound)
23                for digit in range(upper_bound + 1)
24            ) % mod
25            return count_valid_numbers
26
27        # Calculate the count for the upper bound num2
28        current_num = num2
29        count_upper = dfs(0, 0, True)
30      
31        # Clear the cache to avoid using results from the previous dfs calls
32        dfs.cache_clear()
33      
34        # Calculate the count for one less than the lower bound num1,
35        # since we want to include num1 in the result
36        current_num = str(int(num1) - 1)
37      
38        # Compute the count for the adjusted lower bound
39        count_lower = dfs(0, 0, True)
40      
41        # Return the difference modulo mod to ensure no negative values
42        # This will give us the count of valid numbers between num1 and num2
43        return (count_upper - count_lower) % mod
44

1import java.math.BigInteger;
2
3class Solution {
4    private static final int MODULO = (int) 1e9 + 7;
5    private Integer[][] memoizationMatrix;
6    private String upperBoundNumber;
7    private int minSum;
8    private int maxSum;
9
10    public int count(String lowerBound, String upperBound, int minSum, int maxSum) {
11        this.minSum = minSum;
12        this.maxSum = maxSum;
13        upperBoundNumber = upperBound;
14        memoizationMatrix = new Integer[23][220]; // Initialize the memoization matrix
15
16        // Calculate the number of valid numbers less than or equal to upperBound
17        int count = depthFirstSearch(0, 0, true);
18
19        // Calculate the number of valid numbers less than lowerBound by subtracting one from lowerBound
20        upperBoundNumber = new BigInteger(lowerBound).subtract(BigInteger.ONE).toString();
21        memoizationMatrix = new Integer[23][220]; // Reset the memoization matrix for the new upper bound
22        count = (count - depthFirstSearch(0, 0, true) + MODULO) % MODULO; // Adjust count for the range and ensure non-negative result
23
24        return count;
25    }
26
27    private int depthFirstSearch(int position, int currentSum, boolean isLimit) {
28        // Base case: if we've gone through all the digits
29        if (position >= upperBoundNumber.length()) {
30            // Check if the current sum is within the allowed range
31            return (currentSum >= minSum && currentSum <= maxSum) ? 1 : 0;
32        }
33
34        // If this state has already been computed and limit flag is not set, retrieve result from memoization
35        if (!isLimit && memoizationMatrix[position][currentSum] != null) {
36            return memoizationMatrix[position][currentSum];
37        }
38
39        int totalValidNumbers = 0; // This will store the total valid numbers from the current state
40        int upperDigit = isLimit ? upperBoundNumber.charAt(position) - '0' : 9; // Determine the digit to consider based on the limit
41
42        // Loop through all possible digits at the current position
43        for (int digit = 0; digit <= upperDigit; ++digit) {
44            // Recur for the next position, update the current sum, and determine if the limit is still active
45            totalValidNumbers = (totalValidNumbers + depthFirstSearch(position + 1, currentSum + digit, isLimit && digit == upperDigit)) % MODULO;
46        }
47
48        // If the limit flag is not set, save the result in memoization matrix
49        if (!isLimit) {
50            memoizationMatrix[position][currentSum] = totalValidNumbers;
51        }
52
53        return totalValidNumbers;
54    }
55}
56

1#include <cstring>
2#include <functional>
3#include <string>
4
5class Solution {
6public:
7    int count(std::string num1, std::string num2, int minSum, int maxSum) {
8        const int MOD = 1e9 + 7;
9        int memo[23][220]; // Using memo to store computed results (Dynamic Programming)
10        memset(memo, -1, sizeof(memo)); // Initialize memo array with -1
11      
12        // A lambda function for depth-first search which returns the number of ways
13        // The arguments are position (pos), sum (s) and a limit flag (limit) 
14        std::function<int(int, int, bool)> dfs = [&](int pos, int sum, bool limit) -> int {
15            // If we are at the end of the number, check if the sum is within the given range
16            if(pos >= num2.size()) {
17                return (sum >= minSum && sum <= maxSum) ? 1 : 0;
18            }
19            // If this is not a limit case and we have computed this before, return the memoized result
20            if(!limit && memo[pos][sum] != -1) {
21                return memo[pos][sum];
22            }
23            int up = limit ? num2[pos] - '0' : 9; // The max digit we can pick for this position
24            int ans = 0; // Initialize the number of ways to proceed from here
25          
26            // Try every digit from 0 to 'up' and accumulate answer
27            for(int i = 0; i <= up; ++i) {
28                ans += dfs(pos + 1, sum + i, limit && i == up); // Recurse with updated values
29                ans %= MOD; // Ensure the answer stays within the integer range by taking modulo
30            }
31            // If not limit case, save the result in memo
32            if(!limit) {
33                memo[pos][sum] = ans;
34            }
35            return ans;
36        };
37
38        // Calculate the number of ways for the second number
39        int ans = dfs(0, 0, true);
40      
41        // Decrease num1 by 1 (this handles cases where there are leading zeros)
42        for(int i = num1.size() - 1; i >= 0; --i) {
43            if(num1[i] == '0') {
44                num1[i] = '9';
45            } else {
46                num1[i] -= 1;
47                break;
48            }
49        }
50      
51        // Assign num1 to num for second run of dfs
52        num2 = num1;
53        memset(memo, -1, sizeof(memo)); // Reset memo
54        ans -= dfs(0, 0, true); // Calculate the number of ways for the first number and subtract it
55      
56        // Return the answer after ensuring it's positive by adding MOD and taking mod again
57        return (ans + MOD) % MOD;
58    }
59};
60

1// Define constants for modulus to prevent changing its value accidentally.
2const MOD = 1e9 + 7;
3
4// Initialize memoization array globally with appropriate dimensions.
5let memo: number[][] = Array(23)
6    .fill(0)
7    .map(() => Array(220).fill(-1));
8
9// Helper function to perform depth-first search.
10// pos: current position in the string representation of the number.
11// currentSum: the current sum of the digits.
12// isLimit: flag to know if the current recursion is limited by the input numbers.
13const dfs = (pos: number, currentSum: number, isLimit: boolean): number => {
14    // Base case: we reached the end of the number's digits.
15    if (pos >= num.length) {
16      // Check if the sum is within the given range.
17      return currentSum >= minSum && currentSum <= maxSum ? 1 : 0;
18    }
19  
20    // If not limited and we have a computed value, use it.
21    if (!isLimit && memo[pos][currentSum] !== -1) {
22      return memo[pos][currentSum];
23    }
24  
25    let count = 0; // Initialize count for the number of valid numbers.
26    const upperLimit = isLimit ? +num[pos] : 9; // Determine the upper limit for this digit.
27
28    // Try every possible digit for the current position.
29    for (let i = 0; i <= upperLimit; i++) {
30        // Check the next position, updating the sum and limit condition.
31        count = (count + dfs(pos + 1, currentSum + i, isLimit && i === upperLimit)) % MOD;
32    }
33  
34    // If not limited by num's digits, store the computed value.
35    if (!isLimit) {
36      memo[pos][currentSum] = count;
37    }
38  
39    return count;
40};
41
42// Main function to calculate the count of numbers.
43// num1 and num2 are the string representations of the number range.
44// minSum and maxSum define the inclusive range for the sum of digits.
45function count(num1: string, num2: string, minSum: number, maxSum: number): number {
46    let num = num2; // Use num2 to calculate the upper boundary.
47    // Calculate the numbers with sums within [minSum, maxSum] for the upper limit.
48    let resultCount = dfs(0, 0, true);
49  
50    // Decrease num1 by 1 and convert back to string to handle the lower boundary.
51    num = (BigInt(num1) - 1n).toString();
52  
53    // Reset memoization array for the new lower limit calculation.
54    memo = Array(23)
55        .fill(0)
56        .map(() => Array(220).fill(-1));
57  
58    // Calculate the numbers for the lower limit and subtract from the result.
59    resultCount = (resultCount - dfs(0, 0, true) + MOD) % MOD;
60  
61    return resultCount;
62}
63

Time and Space Complexity

The provided code defines a function count which counts the number of integers between two given strings num1 and num2 (inclusive) whose digits sum is between min_sum and max_sum. The function uses a helper function dfs which is cached using the cache decorator from functools.

Time Complexity

The time complexity of the code is determined by the number of different states the dfs function will process. The dfs function takes parameters (pos, s, limit) where:

pos is the current position being considered in the number num,
s is the sum of digits considered so far,
limit is a boolean indicating if the current digits are limited by the original number num.

The key points for determining the time complexity are:

pos can take on len(num) different values where len(num) is the length of num2, which can be considered as n for the purpose of the analysis.
s can vary from 0 to at most 9 * n (in case every digit is a 9).
limit can have 2 different values (True or False).

As such, the total number of states is n * 9n * 2. However, due to the memoization(cache), each state is computed only once. The number of recursive calls made by dfs for each state are bounded by the number of possible digits 0-9, which is 10. Therefore, the time complexity is O(n * 9n * 2 * 10) which simplifies to O(n * 9n).

Space Complexity

The space complexity is determined by the maximum size of the cache and the stack depth due to recursion. Since memoization caches all the possible states of (pos, s, limit):

pos contributes n to the space complexity.
s contributes at most 9 * n.
limit does not significantly increase the space since it's a boolean.

The space complexity for the cache is O(n * 9n). The stack depth will be at most n (since the maximum depth of recursion is the length of the number). Thus, the recursive call stack adds a factor of O(n) to the space complexity.

Combining these, the total space complexity becomes O(n * 9n + n), which simplifies to O(n * 9n) since the second term is dominated by the first.

In conclusion, the time complexity and space complexity of the count function are both O(n * 9n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological Sort

Uniform Cost Search

Monotonic Stack

Memoization

I don’t know