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 10^9 + 7.

Note that digit_sum(x) denotes the sum of the digits of x.

Examples

Example 1

1
2
3

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

1
2
3

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 <= 10^22
  • 1 <= min_sum <= max_sum <= 400

Solution

Method 1 – Digit DP (Dynamic Programming on Digits and Sum)

Intuition

We use digit dynamic programming (digit DP) to count numbers in a range whose digit sum is within a given range. We count all numbers ≤ num2 with valid digit sum, subtract those < num1, and handle leading zeros and tight bounds.

Approach

  1. Define a DP function with parameters: position, current sum, tight (whether the prefix matches the upper bound), and leading_zero.
  2. For each position, try all possible digits (from 0 to the current limit if tight, else 9).
  3. If the sum exceeds max_sum, stop recursion.
  4. If at the end, check if the sum is within [min_sum, max_sum] and not all digits are leading zeros.
  5. Memoize the results for efficiency.
  6. To count in [num1, num2], compute f(num2) - f(num1 - 1).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
public:
    int count(string num1, string num2, int min_sum, int max_sum) {
        return (countGood(num2, min_sum, max_sum) - countGood(dec(num1), min_sum, max_sum) + MOD) % MOD;
    }
    int MOD = 1e9+7;
    int dp[25][410][2][2];
    vector<int> digits;
    int min_sum, max_sum;
    int dfs(int pos, int sum, int tight, int lead) {
        if (sum > max_sum) return 0;
        if (pos == digits.size()) return (!lead && sum >= min_sum && sum <= max_sum) ? 1 : 0;
        int &res = dp[pos][sum][tight][lead];
        if (res != -1) return res;
        res = 0;
        int up = tight ? digits[pos] : 9;
        for (int d = 0; d <= up; ++d) {
            res = (res + dfs(pos+1, sum + d, tight && d==up, lead && d==0)) % MOD;
        }
        return res;
    }
    int countGood(string num, int minS, int maxS) {
        digits.clear();
        for (char c : num) digits.push_back(c-'0');
        memset(dp, -1, sizeof dp);
        min_sum = minS; max_sum = maxS;
        return dfs(0, 0, 1, 1);
    }
    string dec(string s) {
        for (int i = s.size()-1; i >= 0; --i) {
            if (s[i] > '0') { s[i]--; break; } s[i] = '9';
        }
        return s;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public int count(String num1, String num2, int min_sum, int max_sum) {
        return (countGood(num2, min_sum, max_sum) - countGood(dec(num1), min_sum, max_sum) + 1_000_000_007) % 1_000_000_007;
    }
    private int countGood(String num, int min_sum, int max_sum) {
        int n = num.length();
        int[] digits = new int[n];
        for (int i = 0; i < n; i++) digits[i] = num.charAt(i) - '0';
        Integer[][][][] memo = new Integer[n][410][2][2];
        return dp(0, 0, 1, 1, digits, min_sum, max_sum, memo);
    }
    private int dp(int pos, int sum, int tight, int lead, int[] digits, int min_sum, int max_sum, Integer[][][][] memo) {
        if (sum > max_sum) return 0;
        if (pos == digits.length) return (lead == 0 && sum >= min_sum && sum <= max_sum) ? 1 : 0;
        if (memo[pos][sum][tight][lead] != null) return memo[pos][sum][tight][lead];
        int up = tight == 1 ? digits[pos] : 9, res = 0;
        for (int d = 0; d <= up; d++) {
            res = (res + dp(pos+1, sum+d, tight==1 && d==up ? 1 : 0, lead==1 && d==0 ? 1 : 0, digits, min_sum, max_sum, memo)) % 1_000_000_007;
        }
        return memo[pos][sum][tight][lead] = res;
    }
    private String dec(String s) {
        char[] arr = s.toCharArray();
        for (int i = arr.length-1; i >= 0; i--) {
            if (arr[i] > '0') { arr[i]--; break; } arr[i] = '9';
        }
        return new String(arr);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    fun count(num1: String, num2: String, min_sum: Int, max_sum: Int): Int {
        fun countGood(num: String, minSum: Int, maxSum: Int): Int {
            val digits = num.map { it - '0' }
            val n = digits.size
            val memo = Array(n) { Array(410) { Array(2) { Array(2) { -1 } } } }
            fun dp(pos: Int, sum: Int, tight: Int, lead: Int): Int {
                if (sum > maxSum) return 0
                if (pos == n) return if (lead == 0 && sum in minSum..maxSum) 1 else 0
                if (memo[pos][sum][tight][lead] != -1) return memo[pos][sum][tight][lead]
                var res = 0
                val up = if (tight == 1) digits[pos] else 9
                for (d in 0..up) {
                    res = (res + dp(pos+1, sum+d, if (tight == 1 && d == up) 1 else 0, if (lead == 1 && d == 0) 1 else 0)) % 1_000_000_007
                }
                memo[pos][sum][tight][lead] = res
                return res
            }
            return dp(0, 0, 1, 1)
        }
        fun dec(s: String): String {
            val arr = s.toCharArray()
            for (i in arr.indices.reversed()) {
                if (arr[i] > '0') { arr[i]-- ; break } else arr[i] = '9'
            }
            return String(arr)
        }
        return (countGood(num2, min_sum, max_sum) - countGood(dec(num1), min_sum, max_sum) + 1_000_000_007) % 1_000_000_007
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
        MOD = 10**9 + 7
        def count_good(num: str, min_sum: int, max_sum: int) -> int:
            from functools import lru_cache
            digits = list(map(int, num))
            n = len(digits)
            @lru_cache(maxsize=None)
            def dp(pos: int, s: int, tight: bool, lead: bool) -> int:
                if s > max_sum:
                    return 0
                if pos == n:
                    return int(not lead and min_sum <= s <= max_sum)
                up = digits[pos] if tight else 9
                ans = 0
                for d in range(0, up+1):
                    ans = (ans + dp(pos+1, s+d, tight and d==up, lead and d==0)) % MOD
                return ans
            return dp(0, 0, True, True)
        def dec(s: str) -> str:
            s = list(s)
            i = len(s)-1
            while i >= 0:
                if s[i] > '0':
                    s[i] = str(int(s[i])-1)
                    break
                s[i] = '9'
                i -= 1
            return ''.join(s)
        return (count_good(num2, min_sum, max_sum) - count_good(dec(num1), min_sum, max_sum)) % MOD
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

impl Solution {
    pub fn count(num1: String, num2: String, min_sum: i32, max_sum: i32) -> i32 {
        fn count_good(num: &str, min_sum: i32, max_sum: i32) -> i32 {
            let digits: Vec<u8> = num.bytes().map(|b| b - b'0').collect();
            let n = digits.len();
            let mut memo = vec![vec![vec![vec![-1; 2]; 2]; 410]; n];
            fn dp(pos: usize, sum: i32, tight: usize, lead: usize, digits: &[u8], min_sum: i32, max_sum: i32, memo: &mut Vec<Vec<Vec<Vec<i32>>>>) -> i32 {
                if sum > max_sum { return 0; }
                if pos == digits.len() { return if lead == 0 && sum >= min_sum && sum <= max_sum { 1 } else { 0 }; }
                if memo[pos][sum as usize][tight][lead] != -1 { return memo[pos][sum as usize][tight][lead]; }
                let up = if tight == 1 { digits[pos] } else { 9 };
                let mut res = 0;
                for d in 0..=up {
                    res = (res + dp(pos+1, sum+d as i32, if tight == 1 && d == up { 1 } else { 0 }, if lead == 1 && d == 0 { 1 } else { 0 }, digits, min_sum, max_sum, memo)) % 1_000_000_007;
                }
                memo[pos][sum as usize][tight][lead] = res;
                res
            }
            dp(0, 0, 1, 1, &digits, min_sum, max_sum, &mut memo)
        }
        fn dec(s: &str) -> String {
            let mut arr: Vec<u8> = s.bytes().collect();
            for i in (0..arr.len()).rev() {
                if arr[i] > b'0' { arr[i] -= 1; break; } arr[i] = b'9';
            }
            String::from_utf8(arr).unwrap()
        }
        (count_good(&num2, min_sum, max_sum) - count_good(&dec(&num1), min_sum, max_sum) + 1_000_000_007) % 1_000_000_007
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    count(num1: string, num2: string, min_sum: number, max_sum: number): number {
        function countGood(num: string, minSum: number, maxSum: number): number {
            const digits = num.split('').map(Number);
            const n = digits.length;
            const memo = Array.from({length: n}, () => Array.from({length: 410}, () => Array.from({length: 2}, () => Array(2).fill(-1))));
            function dp(pos: number, sum: number, tight: number, lead: number): number {
                if (sum > maxSum) return 0;
                if (pos === n) return lead === 0 && sum >= minSum && sum <= maxSum ? 1 : 0;
                if (memo[pos][sum][tight][lead] !== -1) return memo[pos][sum][tight][lead];
                let res = 0;
                const up = tight === 1 ? digits[pos] : 9;
                for (let d = 0; d <= up; d++) {
                    res = (res + dp(pos+1, sum+d, tight===1 && d===up ? 1 : 0, lead===1 && d===0 ? 1 : 0)) % 1_000_000_007;
                }
                memo[pos][sum][tight][lead] = res;
                return res;
            }
            return dp(0, 0, 1, 1);
        }
        function dec(s: string): string {
            const arr = s.split('');
            for (let i = arr.length-1; i >= 0; i--) {
                if (arr[i] > '0') { arr[i] = String(Number(arr[i])-1); break; } arr[i] = '9';
            }
            return arr.join('');
        }
        return (countGood(num2, min_sum, max_sum) - countGood(dec(num1), min_sum, max_sum) + 1_000_000_007) % 1_000_000_007;
    }
}

Complexity

  • ⏰ Time complexity: O(d * s), where d is the number of digits and s is the max possible digit sum (up to 9*len(num2)).
  • 🧺 Space complexity: O(d * s), for the DP memoization table.