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
andnum2
, inclusive. For example, ifnum1 = "12"
andnum2 = "345"
, a good integerx
could be any number from 12 up to 345. - The digit sum of
x
(the sum of all its digits) is between the rangemin_sum
andmax_sum
, inclusive. For instance, withmin_sum = 2
andmax_sum = 10
, a number like14
with digit sum1 + 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 of3
, 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 bynum2
, we are free to use any digit from0
to9
. If it is bound, we can only use digits up to the corresponding digit innum2
.
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 return1
; otherwise0
. - If we are still building the number, we calculate the upper limit for our current digit (defined by
num2
iflimit
isTrue
, or9
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
and9
are explored (or up to the limit set bynum2
). -
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 to9
, or if we should restrict the digits to those innum2
.
Implementation Walkthrough
- The
dfs
function is defined inside thecount
method since it operates on different versions ofnum
which is stored in a closure. dfs
takes the current position (pos
), the running sum of digits (s
), and a booleanlimit
indicating whether the current path is limited bynum2
.- Base Case: If the
pos
advances past the last digit, it checks ifs
is a good sum (withinmin_sum
andmax_sum
), returning1
or0
as appropriate. - Recursive Case: If not at the end of the number, it considers all digits up to the current digit of
num2
(iflimit
isTrue
) or9
(iflimit
isFalse
). For each digiti
,dfs
is called for the next position with the updated sum and the limit condition updated (it remainsTrue
only ifi
matches the current digit ofnum2
). - Modulo Operation: The sum of the results from
dfs
for different digits at the current position is taken modulo10**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 withnum
set tonum2
, the result stored inans
.- The cache is cleared to reset the memoization table.
dfs
is called again withnum
set to one less thannum1
(bothering string and int representations).- The result of the second
dfs
call is subtracted fromans
to get the count of the good integers that are at leastnum1
. - The return value is
ans % mod
, to ensure the output is within the10**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 EvaluatorExample 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, andlimit
to tell if the current number should be bounded bynum2
. - 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 is21
. We count all good integers up to this point. - We start at position 0 (digit
2
innum2
), with a sum of0
andlimit = True
.- The first digit can only be
1
or2
, as3
would exceednum2
.
- The first digit can only be
- For each possible first digit, we recursively call DFS for the next position.
- At position 1 (when first digit was
1
), we have0 <= next digit <= 9
becauselimit = False
(1 is less than 2).- We check all digits for this position with the first digit fixed to
1
. There are9
possible sequences:10
,11
,12
,13
,14
,15
,16
,17
,18
,19
. However, only13
,14
are "good" since their sums (4
and5
respectively) are within[min_sum, max_sum]
.
- We check all digits for this position with the first digit fixed to
- At position 1 (when the first digit was
2
), nowlimit = True
. We must stay withinnum2
and can now only select the digit0
or1
.- We create sequences
20
and21
, with digit sums of2
and3
respectively. Only21
is "good" as it satisfies our sum constraint.
- We create sequences
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 betweennum1
andnum2
with a digit sum betweenmin_sum
andmax_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 numbernum
,s
is the sum of digits considered so far,limit
is a boolean indicating if the current digits are limited by the original numbernum
.
The key points for determining the time complexity are:
pos
can take onlen(num)
different values wherelen(num)
is the length ofnum2
, which can be considered asn
for the purpose of the analysis.s
can vary from0
to at most9 * n
(in case every digit is a9
).limit
can have2
different values (True
orFalse
).
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
contributesn
to the space complexity.s
contributes at most9 * 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.
Which of these properties could exist for a graph but not a tree?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Don’t Miss This!