[Leetcode]1590. Make Sum Divisible by P

Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. 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, 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/