DCC 03/10/24 || Prefix Sum Solution || Complete Explanation✅✅
Intuition\n- The problem asks us to remove the smallest subarray such that the sum of the remaining elements in the array is divisible by p. If the sum of the e
# Intuition\n- The problem asks us to remove the smallest subarray such that the sum of the remaining elements in the array is divisible by p. If the sum of the entire array is already divisible by p, no subarray needs to be removed, and the answer is 0. However, if it\'s not divisible, we need to remove a subarray such that the remaining sum becomes divisible by p.\n\n- To solve this, we need to find a subarray where removing it results in the desired condition. A key observation is that for the remaining array\'s sum to be divisible by p, the sum of the removed subarray must have a remainder (mod p) that makes the remaining sum divisible by p. This requires careful tracking of prefix sums and their remainders.\n\n# Approach\n**Prefix Sum Calculation:**\n- We first compute the prefix sum preSum of the array, where preSum[i] represents the sum of elements from the beginning of the array up to index i.\nCalculate the total sum of the array and determine the remainder of this sum when divided by p, denoted as mainRem. This remainder is the amount we need to "remove" from a subarray so that the remaining sum becomes divisible by p.\n\n**HashMap to Track Prefix Remainders:**\n- We maintain a hashmap mp that stores the remainder of prefix sums modulo p as keys and the index of their occurrences as values. This allows us to check whether there is a previous prefix sum that, when removed, gives a sum divisible by p.\nWe use the condition `(rem - mainRem + p)%p` to check if removing a subarray will make the remaining sum divisible by p. If this remainder is found in the hashmap, it means that the subarray starting from the index stored in the hashmap to the current index can be removed to satisfy the condition.\n\n**Find Minimum Length:**\n- For every element in the array, we compute the remainder of the current prefix sum % p and check if we can find a previous remainder in the hashmap that forms a valid subarray to remove.\nWe update the minimum length of such a subarray as we iterate through the array.\n\n**Edge Cases:**\n- If the total sum is already divisible by p, `return 0` as no subarray needs to be removed.\nIf it\'s impossible to find a subarray that meets the condition, `return -1`.\n\n# Complexity\n**Time complexity:**\nWe compute the prefix sums in $$O(n)$$ time. The remainder lookups and insertions into the hashmap take $$O(1)$$ on average, so the overall complexity is linear with respect to the size of the input array.\n\n**Space complexity:**\nWe use an extra array to store the prefix sums `(preSum)` and a hashmap to store the remainders and their indices. Both structures take $$O(n)$$ space.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minSubarray(vector<int>& nums, int p) {\n       long long preSum[nums.size()];\n       preSum[0]=nums[0];\n       unordered_map<int,int> mp;\n       int size=nums.size();\n       mp[0]=-1;\n\n       for(int i=1; i<nums.size(); i++){\n         preSum[i]=preSum[i-1]+nums[i];\n       } \n       int mainRem= preSum[(int)nums.size()-1]%p;\n       if(mainRem==0) return 0;\n       if(preSum[nums.size()-1]<p) return -1;\n       for(int i=0; i<nums.size(); i++){\n        int rem= preSum[i]%p;\n        if(mp.find((rem-mainRem+p)%p)!=mp.end()){\n            size=min(size,i-mp[(rem-mainRem+p)%p]);\n        }\n        mp[rem]=i;\n       }\n\n       return (size<nums.size())?size:-1;\n    }\n};\n```
['Array', 'Hash Table', 'Prefix Sum', 'C++']