# Count of Integers
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-of-integers)
Canonical: https://scaleengineer.com/dsa/problems/count-of-integers
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley)
---
## Problem
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 <= num2`
* `min_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 <= 1022`
* `1 <= min_sum <= max_sum <= 400`

# Approaches
## Brute Force Iteration
The most straightforward approach is to simulate the process directly. We can iterate through every integer `x` from `num1` to `num2`, calculate the sum of its digits, and check if this sum falls within the given `[min_sum, max_sum]` range. If it does, we increment a counter. Due to the massive size of `num1` and `num2` (up to 10^22), we must use a data type that can handle arbitrarily large integers, such as `BigInteger` in Java.
**Time:** O((num2 - num1) * L), where L is the average number of digits in the numbers in the range. Given that `num2` can be up to 10^22, this is far too slow. · **Space:** O(L), where L is the number of digits in `num2`. This space is required to store the `BigInteger` representation of the current number.
**Pros:** Easy to understand and implement.; Correct for small ranges of `num1` and `num2`.
**Cons:** Extremely inefficient and will cause a 'Time Limit Exceeded' error on any platform for the given constraints.; The difference between `num2` and `num1` can be very large (up to 10^22), making iteration impossible.
### Explanation
This method involves a simple loop from the starting number `num1` to the ending number `num2`. For each number, we perform a check. The check consists of two parts: calculating the digit sum and comparing it with `min_sum` and `max_sum`. While simple to conceptualize, the number of iterations can be enormous, making this approach computationally infeasible for the constraints of the problem.

```java
import java.math.BigInteger;

// This is a conceptual example that will time out.
class Solution {
    public int count(String num1, String num2, int min_sum, int max_sum) {
        BigInteger current = new BigInteger(num1);
        BigInteger end = new BigInteger(num2);
        long count = 0;
        int MOD = 1_000_000_007;

        while (current.compareTo(end) <= 0) {
            if (isGood(current, min_sum, max_sum)) {
                count++;
            }
            current = current.add(BigInteger.ONE);
        }
        // The count can be large, but the problem asks for the final result modulo 10^9+7.
        // However, since we can't even finish the loop, this is a moot point.
        return (int)(count % MOD);
    }

    private boolean isGood(BigInteger n, int min_sum, int max_sum) {
        String s = n.toString();
        int sum = 0;
        for (char c : s.toCharArray()) {
            sum += c - '0';
            if (sum > max_sum) { // Small optimization
                return false;
            }
        }
        return sum >= min_sum && sum <= max_sum;
    }
}
```
### Algorithm
1. Initialize a counter `count` to 0.
2. Use `BigInteger` to handle the large numbers `num1` and `num2`.
3. Create a loop that iterates from `num1` to `num2`, incrementing by one in each step.
4. For each number in the loop:
   a. Convert the `BigInteger` to a string.
   b. Calculate the sum of its digits by iterating through the string characters.
   c. Check if the calculated digit sum lies within the range `[min_sum, max_sum]`.
   d. If the condition is true, increment the `count`.
5. After the loop finishes, return the final `count`.

## Digit Dynamic Programming
A highly efficient solution for this type of problem is Digit Dynamic Programming. The core idea is to rephrase the problem from counting in a range `[num1, num2]` to finding the count of good numbers up to a certain number `N`. Let's define a function `calculate(S)` that counts good integers in the range `[0, S]`. The answer to the original problem can then be found by `calculate(num2) - calculate(num1 - 1)`. This reduces the problem to implementing the `calculate(S)` function efficiently.

We build the numbers digit by digit from left to right and use memoization to store the results of subproblems, which are defined by the current position, the current sum of digits, and whether we are tightly bound by the digits of the input number `S`.
**Time:** O(L * max_sum * 10), where L is the number of digits in `num2`. Each state is computed once, and computing a state involves a loop of at most 10 iterations. · **Space:** O(L * max_sum), where L is the number of digits in `num2` (at most 22) and `max_sum` is at most 400. This is for the memoization table.
**Pros:** Very efficient and passes the given constraints.; It's a general technique applicable to a wide range of problems involving counting numbers with specific properties up to a large limit.
**Cons:** More complex to understand and implement compared to brute force.; Requires careful handling of states, transitions, and base cases, especially for edge cases like leading zeros and range transformation.
### Explanation
The `calculate(S)` function is implemented using a recursive helper function, say `dp`, with memoization. The state of our DP needs to capture all the information required to make decisions for the subsequent digits.

- **DP State**: `dp(index, currentSum, isTight, isStarted)`
  - `index`: The 0-based index of the digit we are currently placing.
  - `currentSum`: The sum of the digits we have placed so far.
  - `isTight`: A boolean. `true` if we are restricted by the digits of `S` (i.e., we can't place a digit greater than `S[index]`), `false` otherwise. This becomes `false` for future states as soon as we place a digit smaller than the one in `S` at the current `index`.
  - `isStarted`: A boolean. `true` if we have placed at least one non-zero digit. This helps differentiate the number 0 from numbers with leading zeros (e.g., `007` vs `7`).

- **Transitions**: In the `dp` function, we iterate through possible digits for the current `index`. The upper limit for the digit is `S[index]` if `isTight` is true, and 9 otherwise. For each valid digit, we make a recursive call to `dp` for `index + 1` with updated parameters for `currentSum`, `isTight`, and `isStarted`.

- **Base Case**: When `index` reaches the end of the string `S`, we have formed a complete number. If `isStarted` is true and `currentSum` is within `[min_sum, max_sum]`, we have found one good number, so we return 1. Otherwise, we return 0.

- **Range Calculation**: The final result is `(calculate(num2) - calculate(subtractOne(num1)) + MOD) % MOD`. The `subtractOne` function is a helper to get the string representation of `num1 - 1`.

```java
class Solution {
    private static final int MOD = 1_000_000_007;
    private String S;
    private int minSum;
    private int maxSum;
    private Integer[][][][] memo;

    public int count(String num1, String num2, int min_sum, int max_sum) {
        int ans2 = calculate(num2, min_sum, max_sum);
        String num1Minus1 = subtractOne(num1);
        int ans1 = calculate(num1Minus1, min_sum, max_sum);
        return (ans2 - ans1 + MOD) % MOD;
    }

    private int calculate(String s, int min_sum, int max_sum) {
        this.S = s;
        this.minSum = min_sum;
        this.maxSum = max_sum;
        // memo[index][sum][isTight][isStarted]
        this.memo = new Integer[s.length()][max_sum + 1][2][2];
        return dp(0, 0, true, false);
    }

    private int dp(int index, int currentSum, boolean isTight, boolean isStarted) {
        if (index == S.length()) {
            return (isStarted && currentSum >= minSum && currentSum <= maxSum) ? 1 : 0;
        }
        int tightInt = isTight ? 1 : 0;
        int startedInt = isStarted ? 1 : 0;
        if (memo[index][currentSum][tightInt][startedInt] != null) {
            return memo[index][currentSum][tightInt][startedInt];
        }

        long count = 0;
        int upperBound = isTight ? (S.charAt(index) - '0') : 9;

        for (int digit = 0; digit <= upperBound; digit++) {
            boolean newStarted = isStarted || (digit > 0);
            int newSum = currentSum + digit;

            if (newSum <= maxSum) {
                boolean newTight = isTight && (digit == upperBound);
                count = (count + dp(index + 1, newSum, newTight, newStarted)) % MOD;
            }
        }

        return memo[index][currentSum][tightInt][startedInt] = (int) count;
    }

    private String subtractOne(String n) {
        int len = n.length();
        char[] s = n.toCharArray();
        int i = len - 1;
        while (i >= 0) {
            if (s[i] > '0') {
                s[i]--;
                break;
            }
            s[i] = '9';
            i--;
        }
        if (len > 1 && s[0] == '0') {
            return new String(s, 1, len - 1);
        }
        return new String(s);
    }
}
```
### Algorithm
1. The problem of counting in a range `[A, B]` is transformed into `count(B) - count(A-1)`.
2. Implement a function `calculate(S, min_sum, max_sum)` that counts good integers in `[0, S]`.
3. The final answer is `(calculate(num2, ...) - calculate(num1 - 1, ...)) % MOD`. A helper function `subtractOne(S)` is needed for this.
4. `calculate` uses a recursive digit DP approach with memoization. The state is `dp(index, currentSum, isTight, isStarted)`.
   - `index`: Current digit position being filled (from left).
   - `currentSum`: Sum of digits placed so far.
   - `isTight`: Boolean flag indicating if we are restricted by the digits of `S`. If true, the current digit can be at most `S[index]`. If we pick a smaller digit, `isTight` becomes false for subsequent states.
   - `isStarted`: Boolean flag to handle numbers of varying lengths. It's true once a non-zero digit is placed.
5. The `dp` function explores all valid digit choices, making recursive calls for the next state, and sums up the results. Memoization is used to store results of subproblems to avoid recomputation.

# Solutions
### Java

```java
import java.math.BigInteger ; class Solution { private final int mod = ( int ) 1 e9 + 7 ; private Integer [][] f ; private String num ; private int min ; private int max ; public int count ( String num1 , String num2 , int min_sum , int max_sum ) { min = min_sum ; max = max_sum ; num = num2 ; f = new Integer [ 23 ][ 220 ]; int a = dfs ( 0 , 0 , true ); num = new BigInteger ( num1 ). subtract ( BigInteger . ONE ). toString (); f = new Integer [ 23 ][ 220 ]; int b = dfs ( 0 , 0 , true ); return ( a - b + mod ) % mod ; } private int dfs ( int pos , int s , boolean limit ) { if ( pos >= num . length ()) { return s >= min && s <= max ? 1 : 0 ; } if (! limit && f [ pos ][ s ] != null ) { return f [ pos ][ s ]; } int ans = 0 ; int up = limit ? num . charAt ( pos ) - '0' : 9 ; for ( int i = 0 ; i <= up ; ++ i ) { ans = ( ans + dfs ( pos + 1 , s + i , limit && i == up )) % mod ; } if (! limit ) { f [ pos ][ s ] = ans ; } return ans ; } }
```

### CPP

```cpp
class Solution { public: int count ( string num1 , string num2 , int min_sum , int max_sum ) { const int mod = 1e9 + 7 ; int f [ 23 ][ 220 ]; memset ( f , - 1 , sizeof ( f )); string num = num2 ; function < int ( int , int , bool ) > dfs = [ & ]( int pos , int s , bool limit ) -> int { if ( pos >= num . size ()) { return s >= min_sum && s <= max_sum ? 1 : 0 ; } if ( ! limit && f [ pos ][ s ] != - 1 ) { return f [ pos ][ s ]; } int up = limit ? num [ pos ] - '0' : 9 ; int ans = 0 ; for ( int i = 0 ; i <= up ; ++ i ) { ans += dfs ( pos + 1 , s + i , limit && i == up ); ans %= mod ; } if ( ! limit ) { f [ pos ][ s ] = ans ; } return ans ; }; int a = dfs ( 0 , 0 , true ); for ( int i = num1 . size () - 1 ; ~ i ; -- i ) { if ( num1 [ i ] == '0' ) { num1 [ i ] = '9' ; } else { num1 [ i ] -= 1 ; break ; } } num = num1 ; memset ( f , - 1 , sizeof ( f )); int b = dfs ( 0 , 0 , true ); return ( a - b + mod ) % mod ; } };
```

### Python

```python
class Solution : def count ( self , num1 : str , num2 : str , min_sum : int , max_sum : int ) -> int : @ cache def dfs ( pos : int , s : int , limit : bool ) -> int : if pos >= len ( num ): return int ( min_sum <= s <= max_sum ) up = int ( num [ pos ]) if limit else 9 return ( sum ( dfs ( pos + 1 , s + i , limit and i == up ) for i in range ( up + 1 )) % mod ) mod = 10 ** 9 + 7 num = num2 a = dfs ( 0 , 0 , True ) dfs . cache_clear () num = str ( int ( num1 ) - 1 ) b = dfs ( 0 , 0 , True ) return ( a - b ) % mod
```