2719

2719. Count of Integers (Hard)

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

Companies: Amazon, DE Shaw

Related Topics:
Math, String, Dynamic Programming

Hints:

• Let f(n, l, r) denotes the number of integers from 1 to n with the sum of digits between l and r.
• The answer is f(num2, min_sum, max_sum) - f(num-1, min_sum, max_sum).
• You can calculate f(n, l, r) using digit dp.

Solution 1.

Let dp[s][mx] be the count of numbers <= s (s is a number expressed as a string) whose digit sum <= mx.

The answer can be expressed as follows

(dp[t][mx] - dp[t][mn - 1]) - (dp[s1][mx] - dp[s1][mn - 1])

where s1 is the string expression of s - 1.

For dp[s][mx], there are two cases:

1. Let the first digit be s[0], we need to count dp[s[1:]][mx - s[0]]
2. Let the first digit be c < s[0], we need to count dp2[s.size() - 1][mx - c]

Here dp2[len][mx] is the count of numbers of length len whose digit sum <= mx.

dp2[len][mx] = SUM( dp2[len - 1][mx - i] | 0 <= i <= 9 )

// OJ: https://leetcode.com/problems/count-of-integers
// Author: github.com/lzl124631x
// Time: O((M + N) * (Mx + Mn)) where M/N is the length of `s` and `t`.
// Space: O((M + N) * (Mx + Mn))
class Solution {
public:
    int count(string s, string t, int mn, int mx) {
        long mod = 1e9 + 7;
        unordered_map<string, unordered_map<int, long>> m;
        unordered_map<int, unordered_map<int, long>> m2;
        function<long(int, int)> dp2 = [&](int len, int mx) -> long {
            if (len == 1) return max(0, min(mx, 9) + 1);
            if (mx < 0) return 0L;
            if (m2.count(len) && m2[len].count(mx)) return m2[len][mx];
            long ans = 0;
            for (int i = 0; i <= 9; ++i) {
                ans = (ans + dp2(len - 1, mx - i)) % mod;
            }
            return m2[len][mx] = ans;
        };
        function<long(string, int)> dp = [&](string s, int mx) -> long {
            if (s.size() == 1) return max(0, min(s[0] - '0', mx) + 1);
            if (mx < 0) return 0L;
            if (m.count(s) && m[s].count(mx)) return m[s][mx];
            long ans = 0;
            ans = (ans + dp(s.substr(1), mx - s[0] + '0')); // Let the first digit be `s[0]`, count `dp[s[1:]][mx - s[0]]`
            for (char c = s[0] - 1; c >= '0'; --c) {
                ans = (ans + dp2(s.size() - 1, mx - c + '0')) % mod; // Let the first digit be `c < s[0]`, count `dp2[s.size() - 1][mx - c]`
            }
            return m[s][mx] = ans;
        };
        long a = (dp(t, mx) - dp(t, mn - 1) + mod) % mod;
        auto s1 = s;
        int carry = -1;
        for (int i = s1.size() - 1; i >= 0 && carry; --i) {
            if (s1[i] == '0') {
                s1[i] = '9';
            } else {
                s1[i]--;
                carry = 0;
            }
        }
        if (s1[0] == '0' && s1.size() > 1) s1 = s1.substr(1);
        return ((a - dp(s1, mx) + mod) % mod + dp(s1, mn - 1)) % mod;
    }
};