Given an array of positive integers`nums`

, remove thesmallestsubarray (possiblyempty) such that thesumof the remaining elements is divisible by`p`

. It isnotallowed to remove the whole array. Returnthe length of the smallest subarray that you need to remove, or`-1`

if it's impossible. Asubarrayis defined as a contiguous block of elements in the array.

This question is very similar to [Leetcode]560. Subarray Sum Equals K and Leetcode 974. Subarray Sums Divisible by K. It requires two prior knowledge on prefix-sum, hashmap, and a little bit of math.

## Logic

The 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`

.

Similar to [Leetcode]560. Subarray Sum Equals K, there 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 are some prefix sums `prev=sum(arr[0...i]))`

such that:

`sum(arr[i...j])==(cur-prev)%p==sum(arr)%p==target`

.

Therefore, all we need to find is simply `(cur-target)%p`

.

#### Some math

- if
`(a-b)%k==0`

, then`a%k==b%k`

`(a-b)%k == (a%k-b%k)%k`

## Code

class Solution: def minSubarray(self, nums: List[int], p: int) -> int: if sum(nums)%p==0: return 0 target = sum(nums) % p dic,n = {0:-1},len(nums) cur,ret = 0,n for i,num in enumerate(nums): cur = (cur+num)%p if dic.get((cur-target)%p) is not None: ret = min(ret,i-dic.get((cur-target)%p)) dic[cur] = i return ret if ret < n else -1

## Reference

- https://leetcode.com/problems/make-sum-divisible-by-p/
- https://shawnlyu.com/leetcode/leetcode560-subarray-sum-equals-k/