Given an array of positive integersnums
, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible byp
. It is not allowed to remove the whole array. Return the length of the smallest subarray that you need to remove, or-1
if it's impossible. A subarray is 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
, thena%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/