Digit DP DAY1 [ Count Of Integers ] Day1/10
Anonymous User
2669
Career

You are given two numeric strings num1 and num2 and two integers maxsum and minsum. 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

MOD = 10**9 + 7

class Solution:
    def __init__(self):
        self.dp = [[[[-1 for _ in range(401)] for _ in range(2)] for _ in range(2)] for _ in range(23)]

    def countValidStrings(self, pos, isLowerBoundTight, isUpperBoundTight, currentSum, lowerBound, upperBound):
        if currentSum < 0:
            return 0
        if pos == len(upperBound):
            return 1
        if self.dp[pos][isLowerBoundTight][isUpperBoundTight][currentSum] != -1:
            return self.dp[pos][isLowerBoundTight][isUpperBoundTight][currentSum]

        lowerLimit = int(lowerBound[pos]) if isLowerBoundTight else 0
        upperLimit = int(upperBound[pos]) if isUpperBoundTight else 9

        count = 0
        for digit in range(lowerLimit, upperLimit + 1):
            count += self.countValidStrings(pos + 1, isLowerBoundTight and digit == lowerLimit, isUpperBoundTight and digit == upperLimit, currentSum - digit, lowerBound, upperBound)
            count %= MOD

        self.dp[pos][isLowerBoundTight][isUpperBoundTight][currentSum] = count
        return count

    def count(self, lowerBound, upperBound, minSum, maxSum):
        leadingZeroes = len(upperBound) - len(lowerBound)
        lowerBound = '0' * leadingZeroes + lowerBound

        total = self.countValidStrings(0, True, True, maxSum, lowerBound, upperBound)
        unnecessary = self.countValidStrings(0, True, True, minSum - 1, lowerBound, upperBound)
        result = (total - unnecessary + MOD) % MOD

        return result if result >= 0 else result + MOD


const int MOD = 1e9 + 7;

class Solution {
    int dp[23][2][2][401];

    int countValidStrings(int pos, bool isLowerBoundTight, bool isUpperBoundTight, int currentSum, string& lowerBound, string& upperBound) {
        if (currentSum < 0) return 0;
        if (pos == upperBound.size()) return 1;
        if (dp[pos][isLowerBoundTight][isUpperBoundTight][currentSum] != -1) return dp[pos][isLowerBoundTight][isUpperBoundTight][currentSum];

        int lowerLimit = isLowerBoundTight ? lowerBound[pos] - '0' : 0;
        int upperLimit = isUpperBoundTight ? upperBound[pos] - '0' : 9;

        int count = 0;
        for (int digit = lowerLimit; digit <= upperLimit; digit++) {
            count += countValidStrings(pos + 1, isLowerBoundTight & (digit == lowerLimit), isUpperBoundTight & (digit == upperLimit), currentSum - digit, lowerBound, upperBound);
            count %= MOD;
        }

        return dp[pos][isLowerBoundTight][isUpperBoundTight][currentSum] = count;
    }

public:
    int count(string lowerBound, string upperBound, int minSum, int maxSum) {
        memset(dp, -1, sizeof(dp));
        int leadingZeroes = upperBound.length() - lowerBound.length();
        while (leadingZeroes--) {
            lowerBound = '0' + lowerBound;
        }

        int total = countValidStrings(0, true, true, maxSum, lowerBound, upperBound);
        int unnecessary = countValidStrings(0, true, true, minSum - 1, lowerBound, upperBound);
        int result = (total - unnecessary + MOD) % MOD;

        return (result < 0) ? result + MOD : result;
    }
};

  1. Intuition:

    • The code counts the number of strings formed by concatenating digits that fall within a specified range [lowerBound, upperBound].
    • These strings must also satisfy two constraints: the sum of their digits should be between minSum and maxSum.

  2. Algorithm:

    • The code uses dynamic programming (DP) to efficiently count the valid strings within the given range and with the specified sum constraints.

    • It maintains a 4-dimensional DP array dp, where dp[pos][isLowerBoundTight][isUpperBoundTight][currentSum] stores the number of valid strings that can be formed considering the current position pos, whether the lower and upper bounds are tight at this position, and the current sum of digits.

    • The recursive function countValidStrings explores all possible digit choices at each position and updates the DP array accordingly.

    • The main count function initializes the DP array and adjusts the lower bound by adding leading zeroes to make it the same length as the upper bound.

    • It calculates the total number of valid strings within the upper bound and the unnecessary strings within the lower bound (those with a sum less than minSum), and then subtracts the unnecessary ones to get the final count.

I will be Posting Daily Digit DP problems and Solutions Do Upvote If you like it 😊
#DIGITDp10daysOP

Feel free to Post your solution in the comments

Notes :https://docs.google.com/document/d/1O62JC4y3w40A1PNHP21OanJFwEAB3kndQuDu_INuuM0/edit?usp=sharing

Comments (5)