• Posts

Problem 1590 Make Sum Divisible by P

Problem Statement

Link - Problem 1590

Question

Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.

Return the length of the smallest subarray that you need to remove, or -1 if it's impossible.

A subarray is defined as a contiguous block of elements in the array.

Example 1:

Input: nums = [3,1,4,2], p = 6
Output: 1
Explanation: The sum of the elements in nums is 10, 
which is not divisible by 6. We can remove the subarray [4], 
and the sum of the remaining elements is 6, 
which is divisible by 6.

Example 2:

Input: nums = [6,3,5,2], p = 9
Output: 2
Explanation: We cannot remove a single element to get a sum divisible by 9. 
The best way is to remove the subarray [5,2], leaving us with [6,3] with sum 9.

Example 3:

Input: nums = [1,2,3], p = 3
Output: 0
Explanation: Here the sum is 6. which is already divisible by 3. Thus we do not need to remove anything.

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= p <= 109

Solution

class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        int n = nums.size();
        int totalSum = 0;

        for (int num : nums) {
            totalSum = (totalSum + num) % p;
        }

        int target = totalSum % p;
        if (target == 0)
            return 0;

        unordered_map<int, int> modMap;
        modMap[0] = -1;
        int currentSum = 0, minLen = n;

        for (int i = 0; i < n; ++i) {
            currentSum = (currentSum + nums[i]) % p;

            int needed = (currentSum - target + p) % p;

            if (modMap.find(needed) != modMap.end()) {
                minLen = min(minLen, i - modMap[needed]);
            }
            modMap[currentSum] = i;
        }

        return minLen == n ? -1 : minLen;
    }
};

Complexity Analysis

| Algorithm                      | Time Complexity | Space Complexity |
| ------------------------------ | --------------- | ---------------- |
| Sliding Window with Hash Table | O(n)            | O(n)             |

Explanation

Intial Thoughts

To approach this problem, we should first calculate the total sum of the array and its remainder when divided by p. If the remainder is zero, then we don’t need to remove any subarray. We should also think about using a hashmap to store the prefix sums and their indices. We can then iterate over the array, updating the current sum and checking if there’s a prefix sum that can help us find a subarray to remove. Key points to consider are: calculating the total sum, finding the target remainder, using a hashmap for prefix sums, and iterating over the array to find the smallest subarray to remove.

Intuitive Analysis

Intuitively, we can think of this problem as trying to find a ‘balance point’ in the array where removing a subarray would make the remaining sum divisible by p. We can use the concept of prefix sums and modular arithmetic to find this balance point. We should consider the following points: the remainder of the total sum when divided by p gives us the target, we can use a sliding window approach to find the smallest subarray, the hashmap helps us keep track of the prefix sums and their indices, and by iterating over the array and updating the current sum, we can find the smallest subarray that needs to be removed to make the remaining sum divisible by p. Additionally, we should also think about handling edge cases, such as when the smallest subarray to remove is the whole array, in which case we return -1.

1. Intuition

• The problem requires finding the smallest subarray to remove from the given array such that the sum of the remaining elements is divisible by p
• To approach this problem, we first calculate the total sum of the array and find the target sum that needs to be removed
• We use the modulo operator to handle cases where the sum exceeds p
• The key insight is to use a hashmap modMap to store the cumulative sum modulo p and its corresponding index
• This allows us to efficiently find the smallest subarray that needs to be removed
• We iterate through the array, updating the cumulative sum and checking if the required sum is present in the hashmap
• If it is, we update the minimum length of the subarray to be removed

2. Implementation

• We start by calculating the total sum of the array using a for loop: for (int num : nums) { totalSum = (totalSum + num) % p; }
• We then initialize the modMap hashmap with a key of 0 and a value of -1: modMap[0] = -1;
• We iterate through the array, updating the cumulative sum currentSum and checking if the required sum is present in the hashmap: if (modMap.find(needed) != modMap.end()) { minLen = min(minLen, i - modMap[needed]); }
• We use the modulo operator to handle cases where the sum exceeds p: currentSum = (currentSum + nums[i]) % p;
• We update the modMap hashmap with the current cumulative sum and its index: modMap[currentSum] = i;
• Finally, we return the minimum length of the subarray to be removed, or -1 if it’s impossible: return minLen == n ? -1 : minLen;
• The time complexity of this solution is O(n), where n is the length of the input array

Complexity Analysis

Time Complexity:

• The algorithm iterates through the nums array once to calculate the totalSum, resulting in a time complexity of O(n). Then, it iterates through the array again to find the minimum subarray length, adding another O(n) operation. Since these operations are performed sequentially, the overall time complexity is O(n) + O(n) = O(2n), which simplifies to O(n).
• The dominant operations are the two for loops, each with a linear time complexity of O(n). The unordered_map operations, such as find and insert, have an average time complexity of O(1), but can be O(n) in the worst case. However, these operations do not dominate the overall time complexity.
• The time complexity is classified as O(n) because the algorithm performs a constant amount of work for each element in the input array, resulting in a linear time complexity. This classification is justified by the fact that the algorithm’s running time grows linearly with the size of the input array.

Space Complexity:

• The algorithm uses an unordered_map to store the cumulative sums modulo p, resulting in a space complexity of O(n). In the worst case, every element in the input array could be stored in the map, resulting in a maximum size of n.
• The unordered_map data structure has a significant impact on the space complexity, as it stores a separate entry for each unique cumulative sum modulo p. However, the space complexity is still linear because the map size grows linearly with the size of the input array.
• The space complexity is classified as O(n) because the algorithm uses a data structure that stores a linear number of elements, resulting in a space complexity that grows linearly with the size of the input array. This classification is justified by the fact that the algorithm’s memory usage is directly proportional to the size of the input array.

Footnote

This question is rated as Medium difficulty.

Hints

Use prefix sums to calculate the subarray sums.

Suppose you know the remainder for the sum of the entire array. How does removing a subarray affect that remainder? What remainder does the subarray need to have in order to make the rest of the array sum up to be divisible by k?

Use a map to keep track of the rightmost index for every prefix sum % p.

Similar Questions: