Python Prefix Sum Reminder Tracking with Explanation
Let\'s analyze the problem.\n\nThe problem provides us nums (an array of numbers) and a value p and wants us to find a subarry with the smallest length so that 
# Let\'s analyze the problem.\n\nThe problem provides us `nums` (an array of numbers) and a value `p` and wants us to find a subarry with the smallest length so that the sum of other elements can be divided by `p`.\n\nAssuming that the sum of `nums` is `S`, the sum of the target subarray is `S1`, and the sum of other elements in the nums is `S2`. Then, we have` S = S1 + S2`.\n\nNow we know that` S2 % p == 0`, we take modular `p` for equation ` S = S1 + S2`, then we have `S % p = S1 % p`. As `S` is a known number i.e., `sum(nums)`, we here use variable `target` to denote `S % p`. \n\n**After that, the problem becomes finding a subarray with the smallest length and satisfying the equation `S1 % p == target`, where` S1` is the sum of a subarray.**\n\nLet\'s define `prefix_sum[i] = nums[0] + nums[1] + ... + nums[i-1]`, and `S[i,j] =  nums[i] + nums[i+1] + ... + nums[j-1], j > i`\n\nTherefore, the sum of subarray `S[i,j] = prefix_sum[j] - prefix_sum[i] , j > i`.\n\nTake modular for the above equation, we get `S[i,j] % p == (prefix_sum[j] - prefix_sum[i]) % p , j > i`.\n\n**Now, the problems becomes finding indexs i and j so that it satisfying the equation `target == (prefix_sum[j] - prefix_sum[i]) % p , j > i`.**\n\n**Then, we can rewrite the above equation as follows: `(prefix_sum[j] - target) % p == prefix_sum[i] % p, j > i`.**\n\n**_________________________________________________________________________________________________________________________________________________________________________________**\n# Now, we come to the coding part.\n\nTo solve this problem, the trick here is to store the reminder of the prefix sum, instead of the prefix sum itself. \n\nIn particular, we use a dictionary `prefix_reminder_dic` to map the reminder of an element\'s prefix sum to its position - 1, hence `prefix_reminder_dic = {0:-1}`. \n\nWhile we scan the array, we calculate `(reminder - target) % p`, and check if it is already in the `prefix_reminder_dic`. If so, then we found a subarray that satisfies the requirement, and we determine if the length of the subarray `i - prefix_reminder_dic[(reminder - target) % p]` is smaller than the current smallest length, and update the length accordingly.\n\nFinally, we add / update the position for the reminder. (We update the position because the older position will always give us a longer subarrary comparing to the current position.)\n\n**_________________________________________________________________________________________________________________________________________________________________________________**\n# The implementation is here:\n```\nclass Solution:\n    def minSubarray(self, nums: List[int], p: int) -> int:\n        target = sum(nums) % p\n        if target == 0: return 0 # sum(nums) can be divided by p, so no need to remove\n        \n        prefix_reminder_dic = {0:-1} # {reminder -> position - 1}\n        reminder = 0\n        length = len(nums)\n        \n        for i, num in enumerate(nums):\n            reminder = (reminder + num) % p\n            if (reminder - target) % p in prefix_reminder_dic:\n                if i - prefix_reminder_dic[(reminder - target) % p] < length:\n                    length = i - prefix_reminder_dic[(reminder - target) % p]\n            prefix_reminder_dic[reminder] = i\n            \n        return -1 if length == len(nums) else length\n```
['Prefix Sum']