Easy to understand || O(n) complexity 🤓✅
Minimum Subarray to Remove for Divisibility by p\n\nThis document provides a comprehensive overview of the algorithm used to determine the minimum length of a s
# Minimum Subarray to Remove for Divisibility by `p`\n\nThis document provides a comprehensive overview of the algorithm used to determine the minimum length of a subarray that needs to be removed from a given list of integers so that the sum of the remaining elements is divisible by a specified integer `p`.\n\n## Intuition\n\nTo solve the problem of finding the smallest subarray whose removal makes the total sum of the array divisible by `p`, we can leverage the concept of **modular arithmetic** and **prefix sums**:\n\n1. **Total Sum and Remainder:**\n   - Compute the total sum of the array.\n   - Determine the remainder when this sum is divided by `p` (`total % p`). If the remainder is `0`, the array is already divisible by `p`, and no removal is needed.\n\n2. **Target Subarray Sum:**\n   - If the remainder is not `0`, identify a subarray whose sum is equal to this remainder. Removing such a subarray will make the remaining sum divisible by `p`.\n\n3. **Efficient Search for Subarray:**\n   - To efficiently find the smallest such subarray, utilize prefix sums and a hashmap to keep track of the earliest occurrence of each prefix sum modulo `p`. This allows us to identify potential subarrays in linear time.\n\n\n\n# Code\n```python3 []\nclass Solution:\n    def minSubarray(self, nums: List[int], p: int) -> int:\n        remainder = sum(nums) % p\n\n        if remainder == 0:\n            return 0\n\n        target = remainder\n        min_length = len(nums)\n        prefix = 0\n        prefix_map = {0: -1}\n\n        for i, num in enumerate(nums):\n            prefix = (prefix + num) % p\n            needed = (prefix - target) % p\n            if needed in prefix_map:\n                min_length = min(min_length, i - prefix_map[needed])\n            prefix_map[prefix] = i\n\n        return min_length if min_length < len(nums) else -1\n```
['Hash Table', 'Prefix Sum', 'Python3']