Digit DP

2719. Count of Integers

This is the 4th hard question of the LC 348 weekly contest question.

2719. Count of Integers

Explanation

If we can change the problem to the following, it will be easier:

_count(num, min_sum, max_sum) = 
number of numbers in [0, num] whose digit sum is in [min_sum, max_sum]

Then the result will be

_count(num2, min_sum, max_sum) 
- _count(num1, min_sum, max_sum) 
+ whether num1 itself is a valid one

For _count(num, min_sum, max_sum), it is a classical digit DP problem. We just want to be careful when choose the possible digits in current position, specifically, we have two cases:

Use the 10th position when num = 235 as example:

• case 1: what if the 100th position is 2, then we can only choose 0 to 3 for 10th position.
• case 2: if the 100th position is < 2, then we can pick up 0 to 9.

After figuring out those 2 cases, we can use a 3 dimension DP to solve the problem: memo[25][420][2]

• the 25 means maximum lengh of the number. As the number is < 10²², so 25 should be enough.
• The 420 is due to the max digit sum + some buffer. You can argue that the max digit sum should be 25*9, that is also fine.
• The last position is the case 1 and case 2 mentioned above.

C++ solution

From the DP status, we can easily say that the memory and time complexity is

O(25*400*2*10) which is about O(200,000)

const int MOD = 1e9 + 7;
const int PREV_IS_MAX_DIGIT = 1, PREV_LESS_MAX_DIGIT = 0;
class Solution {
    public:
    long long memo[25][420][2];
    long long _count(string &num, int min_sum, int max_sum){
        // count the number of digit sum in [min_sum, max_sum] for nums in [0, num]
        memset(memo, 0, sizeof memo);
        const int n = num.size();
        // 1 means the previous digit reaches the largest digit value as the previous position is 0 for example, 19, 
        // it can be written as 019, so the previous position is 0. It reaches its maximum value. So we set it as 1.
        memo[0][0][PREV_IS_MAX_DIGIT] = 1;
        for (int i = 0;  i < n; ++i) {
            for (int j = 0; j < 9*n; ++j){
                // the third position of the dp memo
                // PREV_LESS_MAX_DIGIT means not reach the largest digit value
                // PREV_IS_MAX_DIGIT means the previous digit reaches the largest digit value

                //PREV_IS_MAX_DIGIT: previous digit reach the largest digit value
                for (int digit = 0; digit < num[i] - '0'; ++digit){
                    memo[i+1][j + digit][PREV_LESS_MAX_DIGIT] +=  memo[i][j][PREV_IS_MAX_DIGIT];
                    memo[i+1][j + digit][PREV_LESS_MAX_DIGIT] %= MOD;
                }
                memo[i+1][j +  num[i] - '0'][PREV_IS_MAX_DIGIT] +=  memo[i][j][PREV_IS_MAX_DIGIT];
                memo[i+1][j +  num[i] - '0'][PREV_IS_MAX_DIGIT] %= MOD;
                // PREV_LESS_MAX_DIGIT previous digit does not reach the largest digit value, for this digit, we can pick up 0 to 9.
                for (int digit = 0; digit < 10; ++digit){
                    memo[i+1][j + digit][PREV_LESS_MAX_DIGIT] +=  memo[i][j][PREV_LESS_MAX_DIGIT];
                    memo[i+1][j + digit][PREV_LESS_MAX_DIGIT] %= MOD;
                }
            }
        }
        long long ret = 0;
        for (int i = min_sum; i <= max_sum; ++i){
            ret += memo[n][i][PREV_LESS_MAX_DIGIT];
            ret += memo[n][i][PREV_IS_MAX_DIGIT];
        }
        return ret % MOD;


    }
    int get_digit_sum(string& num){
        int ret = 0;
        for (auto c: num) ret += c - '0';
        return ret;
    }
    int count(string num1, string num2, int min_sum, int max_sum) {
        long long ret = _count(num2, min_sum, max_sum) -  _count(num1, min_sum, max_sum);
        //cout << ret << endl;
        int digit_sum = get_digit_sum(num1);
        ret += digit_sum >= min_sum && digit_sum <= max_sum;
        return (ret % MOD + MOD) % MOD;
    }
};

Thanks. You can check the list of all my post from my personal blog.

Suggestions from ChatGPT about how to solve digit DP problems?

“

To solve digital dynamic programming (DP) problems, you can follow these general steps:

1. Understand the problem: Read the problem statement carefully and make sure you understand the requirements and constraints.

2. Identify the subproblems: Break down the problem into smaller subproblems. For digital DP problems, the subproblems often involve digits or binary representation of numbers.

3. Define the state: Determine the state that needs to be stored for each subproblem. It could be the current position, the current digit, or any other relevant information.

4. Formulate the recurrence relation: Determine how the solution to a subproblem relates to the solutions of its smaller subproblems. This recurrence relation is typically the key to solving DP problems.

5. Initialize the base cases: Identify the base cases, which are the simplest subproblems that can be solved directly.

6. Implement the DP algorithm: Use the recurrence relation and the initial base cases to iteratively compute the solutions to larger subproblems until you reach the final problem.

7. Optimize the algorithm: Look for opportunities to optimize the algorithm by reducing redundant computations or using memoization techniques.

8. Analyze the time and space complexity: Evaluate the efficiency of your algorithm in terms of time and space complexity.

9. Test and debug: Test your implementation with various test cases to ensure it produces correct results. Debug any errors or logical mistakes that may arise.

By following these steps, you can approach digital DP problems and effectively solve them. Practice and exposure to different problem variations will enhance your understanding and proficiency in solving these types of problems.”