Make Sum Divisible by P

Leetcode Problem:

• Make Sum Divisible by P

Summary

• Given an array of positive integers and a divisor, find the length of the smallest subarray that needs to be removed to make the sum of the remaining elements divisible by the divisor.

Approach

• The solution uses a sliding window approach and a hash map to keep track of the prefix sum modulo the divisor
• It iterates through the array, updating the prefix sum and the hash map, and at each step, it checks if there is a previous prefix sum that is congruent to the current prefix sum minus the needed prefix sum modulo the divisor
• If such a prefix sum exists, it updates the result with the minimum length of the subarray that needs to be removed.

Complexity

• O(n), where n is the length of the array, because each element in the array is processed once.

Explain

• The solution starts by initializing the result with the length of the array, the needed prefix sum, and the current prefix sum
• It then iterates through the array, updating the current prefix sum and the hash map
• At each step, it checks if there is a previous prefix sum that is congruent to the current prefix sum minus the needed prefix sum modulo the divisor
• If such a prefix sum exists, it updates the result with the minimum length of the subarray that needs to be removed
• Finally, it returns the result, which is either the minimum length of the subarray that needs to be removed or -1 if it is impossible to make the sum of the remaining elements divisible by the divisor.

Solution Code:

class Solution {
public:
    
      int minSubarray(vector& A, int p) {
        int n = A.size(), res = n, need = 0, cur = 0;
        for (auto a : A)
            need = (need + a) % p;
        unordered_map last = {{0, -1}};
        for (int i = 0; i < n; ++i) {
            cur = (cur + A[i]) % p;
            last[cur] = i;
            int want = (cur - need + p) % p;
            if (last.count(want))
                res = min(res, i - last[want]);
        }
        return res < n ? res : -1;
    }
};