C++ Solution || Easy to Understand
Intuition\nThe problem asks to find the smallest subarray that can be removed so that the sum of the remaining array is divisible by a given integer p. To achie
# Intuition\nThe problem asks to find the smallest subarray that can be removed so that the sum of the remaining array is divisible by a given integer `p`. To achieve this, we first calculate the remainder of the entire array sum when divided by `p`. Then, we aim to remove the smallest subarray whose sum leaves a remainder that makes the overall sum divisible by `p`.\n\n# Approach\n1. **Calculate Total Remainder**:\n    - First, we calculate the sum of the array and its remainder when divided by `p`. Let this remainder be target.\n2. **Edge Case**:\n    - If `target == 0`, then the total sum is already divisible by `p`, and no subarray needs to be removed, so the answer is `0`.\n3. **Using a HashMap for Efficient Lookup**:\n    - We can solve this problem efficiently using a hashmap (`mp`) to store the remainder of the prefix sums and their indices.\n    - Traverse through the array while maintaining a running prefix sum (`curr`). For each element, calculate the remainder that would make the total sum divisible by `p`. This remainder can be found using `(curr - target + p) % p`.\n    - If the remainder exists in the hashmap, it indicates that a subarray from that index to the current index can be removed to make the remaining sum divisible by `p`.\n    - Update the result by comparing the current subarray length (`j - mp[remain]`).\n4. **Final Result**:\n    - If we find a valid subarray, return its length. If no such subarray exists, return `-1`.\n\n# Complexity\n- Time complexity: $$O(n)$$ \n\n- Space complexity: $$O(n)$$\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minSubarray(vector<int>& nums, int p) {\n        int n = nums.size();\n        int SUM = 0;\n\n        for(int &num : nums) {\n            SUM = (SUM + num) % p;\n        }\n\n        int target = SUM%p;\n\n        if(target == 0) {\n            return 0;\n        }\n\n        unordered_map<int, int> mp;\n\n        int curr = 0;\n        mp[0] = -1;\n\n        int result = n;\n        for(int j = 0; j < n; j++) {\n            curr = (curr + nums[j]) % p;\n\n            int remain = (curr - target + p) % p;\n            if(mp.find(remain) != mp.end()) {\n                result = min(result, j - mp[remain]);\n            }\n\n            mp[curr] = j;\n        }\n\n        return result == n ? -1 : result;\n\n    }\n};\n```\n\n![1721315779911.jpeg](https://assets.leetcode.com/users/images/0dd84b78-38f9-4b38-a4fd-62e8b86e811b_1727963032.8717904.jpeg)\n
['Array', 'Hash Table', 'Prefix Sum', 'C++']