Easy Solution || unordered_map
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires finding the smallest subarray that can be removed from nums such t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires finding the smallest subarray that can be removed from nums such that the sum of the remaining array is divisible by `p`. The key observation here is that to make the sum divisible by `p`, we need to remove a subarray whose sum is congruent to the remainder of the total sum modulo p.\n\nIf the total sum is `S` and `S % p != 0`, we need to find a subarray whose sum, when removed, reduces the total sum to something divisible by p.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Calculate Total Sum and Remainder:**\nFirst, compute the sum of all elements in `nums`. If the sum is already divisible by `p` (i.e., `sum % p == 0`), then return 0 because no subarray needs to be removed.\nOtherwise, compute the remainder `r = sum % p`. Our goal is to find the smallest subarray that has a sum equal to `r` modulo `p` so that removing this subarray makes the sum divisible by `p`.\n\n2. **Use a Unordered Map to Track Prefix Sums:**\nWe use prefix sums modulo `p` to efficiently find subarrays whose sum satisfies the condition.\nMaintain a running prefix sum (modulo `p`) as we iterate through the array. For each element `nums[i]`, calculate the current prefix sum mod p, and then determine what remainder would make the array divisible by p if we removed it.\n\n3. **Leverage Modular Arithmetic:**\nAt each step, compute the required mod (difference between the current prefix mod and the total remainder) and check if it exists in the unodered map. This checks if there\'s a subarray starting from the previous occurrence of this mod that can be removed.\nUse the map to store the smallest index where a particular mod has been seen.\n\n4. **Sliding Window Technique:**\nThe difference between indices where the prefix mod conditions are met gives the length of the subarray that can be removed.\nUpdate the minimum length whenever a valid subarray is found.\n\n5. **Return the Result:**\nIf no valid subarray is found, return `-1`, otherwise return the minimum length.\n\n# Complexity\n- Time complexity: `O(n)`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: `O(n)`\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minSubarray(vector<int>& nums, int p) {\n        long sum = 0;\n        //int minLen = 0;\n        for(int num : nums)\n            sum += num;\n        \n        int remainder = sum % p;\n        if(remainder == 0)\n            return 0;\n        \n        int len = nums.size();\n        unordered_map<int, int> mp;\n        mp[0] = -1;\n\n        int currentMod = 0;\n        for(int i = 0; i < nums.size(); i++){\n            currentMod = (currentMod + nums[i]) % p;\n            int requiredMod = (currentMod - remainder + p) % p;\n            if(mp.find(requiredMod) != mp.end()){\n                len = min(len, i - mp[requiredMod]);\n            }\n            mp[currentMod] = i;\n        }\n        return len == nums.size() ? -1: len;\n    }\n};\n```
['Array', 'Hash Table', 'C++']