Simple and Easy to understand | Beats 93% | Python | CPP | Java
Intuition\nThe problem asks to remove the smallest subarray so the sum of the remaining elements is divisible by p. If the total sum is already divisible by p, 
# Intuition\nThe problem asks to remove the smallest subarray so the sum of the remaining elements is divisible by `p`. If the total sum is already divisible by `p`, no removal is needed. Otherwise, we need to remove a subarray whose sum has the same remainder as the total sum modulo `p`. By tracking prefix sums and their remainders with a hash map, we can efficiently check if removing a subarray can achieve the desired divisibility. The goal is to find the smallest such subarray, leveraging modular arithmetic and prefix sums for optimal performance.\n\n\n# Approach\n1. **Total Sum and Remainder**: Calculate the sum of the array and its remainder when divided by `p`. If the remainder is `0`, return `0` (no subarray needed).\n\n2. **Prefix Sum and Hash Map**: Track the running prefix sum and its modulo `p` in a hash map, storing indices for quick lookup.\n\n3. **Check for Removals**: For each index, check if removing a subarray can make the remaining sum divisible by `p` by finding the target remainder in the hash map.\n\n4. **Return Result**: Return the length of the smallest valid subarray, or `-1` if no such subarray exists.\n# Complexity\n- Time complexity:\n$$O(N)$$\n\n- Space complexity:\n$$O(N)$$\n\n# Code\n```python3 []\nclass Solution:\n    def minSubarray(self, nums: List[int], p: int) -> int:\n        total_sum = sum(nums)  # Calculate total sum of the array\n        remainder = total_sum % p  # Find the remainder when total sum is divided by p\n\n        # If the total sum is already divisible by p, return 0 (no subarray needs to be removed)\n        if remainder == 0:\n            return 0\n\n        def find_smallest_subarray(nums, p, remainder):\n            prefix_sum = 0\n            min_length = len(nums)  # Initialize the minimum length of the subarray\n            prefix_map = {0: -1}  # Store prefix sums modulo p with their indices\n\n            for i, num in enumerate(nums):\n                prefix_sum += num\n                target_remainder = (prefix_sum % p - remainder) % p\n\n                # If target_remainder exists in prefix_map, calculate subarray length\n                if target_remainder in prefix_map:\n                    min_length = min(min_length, i - prefix_map[target_remainder])\n\n                # Update prefix_map with the current prefix_sum % p\n                prefix_map[prefix_sum % p] = i\n\n            return min_length\n\n        smallest_subarray_length = find_smallest_subarray(nums, p, remainder)\n\n        # If smallest_subarray_length is equal to the array length, return -1, otherwise return it\n        return smallest_subarray_length if smallest_subarray_length < len(nums) else -1\n```\n```cpp []\nclass Solution {\npublic:\n    int minSubarray(vector<int>& nums, int p) {\n        long long totalSum = 0;  // Use long long to avoid overflow\n        for (int num : nums) {\n            totalSum += num;\n        }\n        int remainder = totalSum % p;\n\n        // If the total sum is already divisible by p, return 0\n        if (remainder == 0) {\n            return 0;\n        }\n\n        return findSmallestSubarray(nums, p, remainder);\n    }\n\nprivate:\n    int findSmallestSubarray(vector<int>& nums, int p, int remainder) {\n        long long prefixSum = 0;  // Use long long to avoid overflow\n        int minLength = nums.size();\n        unordered_map<int, int> prefixMap;\n        prefixMap[0] = -1;  // Initial condition for no subarray\n\n        for (int i = 0; i < nums.size(); i++) {\n            prefixSum += nums[i];\n            int targetRemainder = (prefixSum % p - remainder + p) % p;\n\n            if (prefixMap.find(targetRemainder) != prefixMap.end()) {\n                minLength = min(minLength, i - prefixMap[targetRemainder]);\n            }\n\n            prefixMap[prefixSum % p] = i;\n        }\n\n        return minLength < nums.size() ? minLength : -1;\n    }\n};\n```\n```java []\nimport java.util.HashMap;\n\npublic class Solution {\n    public int minSubarray(int[] nums, int p) {\n        int totalSum = 0;\n        for (int num : nums) {\n            totalSum += num;\n        }\n        int remainder = totalSum % p;\n\n        // If the total sum is already divisible by p, return 0\n        if (remainder == 0) {\n            return 0;\n        }\n\n        return findSmallestSubarray(nums, p, remainder);\n    }\n\n    private int findSmallestSubarray(int[] nums, int p, int remainder) {\n        int prefixSum = 0;\n        int minLength = nums.length;\n        HashMap<Integer, Integer> prefixMap = new HashMap<>();\n        prefixMap.put(0, -1);  // Initial condition for no subarray\n\n        for (int i = 0; i < nums.length; i++) {\n            prefixSum += nums[i];\n            int targetRemainder = (prefixSum % p - remainder + p) % p;\n\n            if (prefixMap.containsKey(targetRemainder)) {\n                minLength = Math.min(minLength, i - prefixMap.get(targetRemainder));\n            }\n\n            prefixMap.put(prefixSum % p, i);\n        }\n\n        return minLength < nums.length ? minLength : -1;\n    }\n}\n```
['Array', 'Hash Table', 'Prefix Sum', 'C++', 'Java', 'Python3']