You are given two numeric strings num1 and num2 and two integers max_sum and min_sum. We denote an integer x to be good if:
num1 <= x <= num2min_sum <= digit_sum(x) <= max_sum.Return the number of good integers. Since the answer may be large, return it modulo 109 + 7.
Note that digit_sum(x) denotes the sum of the digits of x.
Example 1:
Input: num1 = "1", num2 = "12", min_sum = 1, max_sum = 8
Output: 11
Explanation: There are 11 integers whose sum of digits lies between 1 and 8 are 1,2,3,4,5,6,7,8,10,11, and 12. Thus, we return 11.
Example 2:
Input: num1 = "1", num2 = "5", min_sum = 1, max_sum = 5
Output: 5
Explanation: The 5 integers whose sum of digits lies between 1 and 5 are 1,2,3,4, and 5. Thus, we return 5.
Constraints:
1 <= num1 <= num2 <= 10221 <= min_sum <= max_sum <= 400Problem Overview: You are given two numeric strings num1 and num2. Count how many integers in the inclusive range satisfy a constraint where the sum of their digits falls between min_sum and max_sum.
Approach 1: Iterative Brute Force (O(R * d) time, O(1) space)
The direct method iterates through every integer from num1 to num2. For each number, compute the digit sum and check whether it lies between min_sum and max_sum. If the range size is R and each number has up to d digits, the cost is O(R * d). This works only for small ranges because the numbers can be very large (up to 1022). The approach mainly demonstrates the baseline logic: convert each number to a string or repeatedly extract digits to compute the sum.
Approach 2: Digit Dynamic Programming (Digit DP) (O(d * maxSum * 10) time, O(d * maxSum) space)
The efficient solution counts valid numbers without enumerating them. Instead of iterating through the range, compute how many valid integers exist from 0 to a bound using digit DP, then subtract results: count(num2) - count(num1 - 1). The DP state typically tracks (position, currentSum, tight). position indicates the current digit index, currentSum tracks the accumulated digit sum, and tight indicates whether the prefix is restricted by the upper bound.
At each digit, try placing digits from 0 to the allowed limit. Update the running digit sum and propagate the tight constraint if the chosen digit matches the bound digit. Memoization avoids recomputing states. Because the number of digits is small and the sum range is bounded, the total states remain manageable.
This technique is common in problems involving numeric ranges and digit properties. It combines ideas from dynamic programming, math, and string processing to efficiently explore all valid numbers.
Recommended for interviews: Digit DP is the expected solution. Brute force shows you understand the problem constraints, but it fails for large ranges. Implementing a memoized digit DP demonstrates strong control over state design, boundary handling, and optimization.
This method involves iterating over each integer between num1 and num2, calculating their digit sums, and counting those within the given range. Though simple, this approach considers each number individually and checks if it satisfies the conditions.
This solution in C involves iterating over each number from num1 to num2 and computing their digit sums. If the digit sum is within the specified range, the count is incremented. This code uses primitive handling for large numbers using strings since C does not inherently support very large integers.
The time complexity is O(N*M) where N is the range of numbers and M is the number of digits due to string manipulations, and the space complexity is O(1).
This approach uses dynamic programming concepts, specifically digit-based dynamic programming, to efficiently compute the number of good integers by understanding properties of digit sums and bounds. By breaking the number problem into subproblems per digit, we reduce unnecessary recalculation.
This dynamic programming solution for C++ leverages digit-based DP to efficiently count valid integers in a range without iterating through all possible numbers. This approach uses state parameters in a recursive function to track the digit position, the current digit sum, and whether the current number representation is 'tight' or bound to the actual number.
The time complexity is O(D*sum_bound*TightStates), where D is the number of digits, and TightStates is typically 2, representing tight and non-tight bounds. The space complexity is O(D*sum_bound*TightStates) due to the DP storage.
The problem is actually asking for the number of integers in the range [num1,..num2] whose digit sum is in the range [min_sum,..max_sum]. For this kind of range [l,..r] problem, we can consider transforming it into finding the answers for [1,..r] and [1,..l-1], and then subtracting the latter from the former.
For the answer to [1,..r], we can use digit DP to solve it. We design a function dfs(pos, s, limit), which represents the number of schemes when we are currently processing the posth digit, the digit sum is s, and whether the current number has an upper limit limit. Here, pos is enumerated from high to low.
For dfs(pos, s, limit), we can enumerate the value of the current digit i, and then recursively calculate dfs(pos+1, s+i, limit \bigcap i==up), where up represents the upper limit of the current digit. If limit is true, then up is the upper limit of the current digit, otherwise up is 9. If pos is greater than or equal to the length of num, then we can judge whether s is in the range [min_sum,..max_sum]. If it is, return 1, otherwise return 0.
The time complexity is O(10 times n times max_sum), and the space complexity is O(n times max_sum). Here, n represents the length of num.
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Iterative Brute Force | The time complexity is O(N*M) where N is the range of numbers and M is the number of digits due to string manipulations, and the space complexity is O(1). |
| Dynamic Programming with Digit DP | The time complexity is O(D*sum_bound*TightStates), where D is the number of digits, and TightStates is typically 2, representing tight and non-tight bounds. The space complexity is O(D*sum_bound*TightStates) due to the DP storage. |
| Digit DP | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Brute Force | O(R * d) | O(1) | Only when the numeric range is very small and numbers fit standard integer limits |
| Digit Dynamic Programming (Digit DP) | O(d * maxSum * 10) | O(d * maxSum) | Large ranges with digit constraints; standard technique for counting numbers with digit properties |
Digit DP | 2719. Count of Integers | Leetcode Weekly Contest 348 • codingMohan • 2,863 views views
Watch 4 more video solutions →Practice Count of Integers with our built-in code editor and test cases.
Practice on FleetCode