Python solution for dummies | Intuition+explaination
This is a hard one but I\'ll try my best to explain.\nMathematical background:\n1. If a%p = c = b%p, then (a-b)%p = 0\n\tSketch of proof:\n\t\ta%p = r implies a
This is a hard one but I\'ll try my best to explain.\n**Mathematical background:**\n1. *If a%p = c = b%p, then (a-b)%p = 0*\n\tSketch of proof:\n\t\ta%p = r implies a = (n1)p+r\n\t\tb%p = r implies b = (n2)p+r\n\t\tTherefore, (a-b) = (n1-n2)p, which must be divisible by p\n2. If a-b = c and a%p = r1, c%p = r2, then b%p = r1-r2\n\tSketch of proof:\n\t\ta%p = r1 implies a = (n1)p+r1\n\t\tc%p = r2 implies c = (n2)p+r2\n\t\tTherefore, b%p = (a-c)%p = ((n1)p+r1-(n2)p+r2)%p = ((n1-n2)p+r1+r2)%p = r1+r2\n\n**Intuition:**\nUsing these two relationships, we can start to see how this problem can be tackled.\nOur goal is to remove the smallest subarray such that the sum of the remaining elements is divisible by p. \n\nHow do we know if the remaining sum is divisible by p? i.e. Which subarray should we remove to make the remaining subarray divisible by p?  A brute force way would be trying out all possible subarrays in O(n^2) time, then compute their sum in O(n) time, remove it and see if what remains is divisible by p. This is way too slow. \n\nUsually when we have a question that involves summation of some continous subarray, we resort to prefix sums. This lowers the time complexity of computing subarray summations to O(1), as sum(i, j) = sum(0, j) - sum(0, i-1).\n\nNow that we can compute subarray summation efficiently, we can use the first relationship in the mathematical background: **Suppose the residual of the entire array is r0, we need to find a subarray whose residual is also r0, this way after removing it the remaining subarray would be divisible by p.**\n\nNow our goal is to find the smallest subarray which satisfies:\n**sum(subarray)%p = r0**\n\nOne way to do it is to iterate through the array and use each element as the right end point of the subarray to be removed, then look to the left to find a right end point. This will work but we can do better using the second relationship from the mathematical background. \n\nSimilar to 2sum, as we are iterating through the array, we can use a hashmap/dict to record the index of last appearance of different residuals. Since we are constantly updating and using the last index, we can be sure that the length of the subarray to be removed will be the smallest.\n\nFinally, since cur_residual-tar_residual may be negative, we need to mod it again by p so that it returns the correct result.\n\n```\nfrom collections import defaultdict\nclass Solution:\n    def minSubarray(self, nums: List[int], p: int) -> int:\n        tar_residual = sum(nums)%p\n        if tar_residual == 0:\n            return 0\n        \n        # now find the smallest subarray which satisfies:\n        # sum(subarray)%p = tar_residual\n        prefix_sum, ret = 0, len(nums)\n        residual2lastIdx = defaultdict(int)\n        residual2lastIdx[0] = -1\n        \n        for i, num in enumerate(nums):\n            prefix_sum += num\n            cur_residual = prefix_sum%p\n            d = (cur_residual-tar_residual)%p\n            if d in residual2lastIdx:\n                ret = min(ret, i-residual2lastIdx[d])\n            residual2lastIdx[cur_residual] = i\n           \n        return ret if ret < len(nums) else -1\n            \n\n```
['Python', 'Python3']