Watch 5 video solutions for Count of Integers, a hard level problem involving Math, String, Dynamic Programming. This walkthrough by codingMohan has 2,863 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |