2719. Count of Integers LeetCode Solution

In this guide, you will get 2719. Count of Integers LeetCode Solution with the best time and space complexity. The solution to Count of Integers problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count of Integers solution in C++
Count of Integers solution in Java
Count of Integers solution in Python
Additional Resources

2719. Count of Integers LeetCode Solution image

Problem Statement of Count of Integers

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

Complexity Analysis

Time Complexity: O(|\texttt{num2}| \cdot \texttt{max\_sum} \cdot 2^2 \cdot 10)
Space Complexity: O(|\texttt{num2}| \cdot \texttt{max\_sum} \cdot 2^2)

2719. Count of Integers LeetCode Solution in C++

class Solution {
 public:
  int count(string num1, string num2, int min_sum, int max_sum) {
    const string num1WithLeadingZeros =
        string(num2.length() - num1.length(), '0') + num1;
    vector<vector<vector<vector<int>>>> mem(
        num2.length(),
        vector<vector<vector<int>>>(
            max_sum + 1, vector<vector<int>>(2, vector<int>(2, -1))));
    return (count(num1WithLeadingZeros, num2, 0, max_sum, true, true, mem) -
            count(num1WithLeadingZeros, num2, 0, min_sum - 1, true, true, mem) +
            kMod) %
           kMod;
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  // Returns the number of valid integers, considering the i-th digit, where
  // `sum` is the maximum digit sum, `isTight1` indicates if the current digit
  // is tightly bound for `num1` and `isTight2` indicates if the current digit
  // is tightly bound for `num2`
  int count(const string& num1, const string& num2, int i, int sum,
            bool isTight1, bool isTight2,
            vector<vector<vector<vector<int>>>>& mem) {
    if (sum < 0)
      return 0;
    if (i == num2.length())
      return 1;
    if (mem[i][sum][isTight1][isTight2] != -1)
      return mem[i][sum][isTight1][isTight2];

    int res = 0;

    const int minDigit = isTight1 ? num1[i] - '0' : 0;
    const int maxDigit = isTight2 ? num2[i] - '0' : 9;
    for (int d = minDigit; d <= maxDigit; ++d) {
      const bool nextIsTight1 = isTight1 && (d == minDigit);
      const bool nextIsTight2 = isTight2 && (d == maxDigit);
      res += count(num1, num2, i + 1, sum - d, nextIsTight1, nextIsTight2, mem);
      res %= kMod;
    }

    return mem[i][sum][isTight1][isTight2] = res;
  }
};
/* code provided by PROGIEZ */