How to approach this kind of problem - mind map
If you are new to this kind of problems, you would probably get confused. No worries! Here are list of some prior knowledge you may want to go through before to
If you are new to this kind of problems, you would probably get confused. No worries! Here are list of some prior knowledge you may want to go through before touching it.\n\n- [Leetcode 560. Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/)\nso that you know how to use prefix sum and hashmap to reduce the time complexity from O(n^2) to O(n)\n- [Leetcode 974. Subarray Sums Divisible by K](https://leetcode.com/problems/subarray-sums-divisible-by-k/)\nso that you know how to deal with Modulo operation\n\nLogic\n\n![image](https://assets.leetcode.com/users/images/af561ed1-860b-4e7e-a3d1-c034d5ebb18f_1600562111.4748287.png)\n\n\nThe question asks for removing a subarray from ```arr``` such that the sum of the remaining array is divisible by ```p```. As shown above, this question could be converted to another question: find one subarray such that the sum of it equals to the ```sum(arr)%p```.\n\nthere are O(n^2) subarrays and to reduce the time complexity to O(n), we have to borrow some space. While we are calculating the running/accumulated sum ```cur==sum(arr[0...j))```, we hope there is some prefix sum ```prev=sum(arr[0...i]))``` such that: ```sum(arr[i...j])==(cur-prev)%p==sum(arr)%p==target```\n\nTherefore, all we need to find is simply ```(cur-target)%p```.\n\nCode\n\n```Python\nclass Solution:\n    def minSubarray(self, nums: List[int], p: int) -> int:\n        if sum(nums)%p==0:\n            return 0\n        target = sum(nums) % p\n        dic,n = {0:-1},len(nums)\n        cur,ret = 0,n\n        for i,num in enumerate(nums):\n            cur = (cur+num)%p\n            if dic.get((cur-target)%p) is not None:\n                ret = min(ret,i-dic.get((cur-target)%p))\n            dic[cur] = i\n        return ret if ret < n else -1\n```\n\n
['Python3']