Leetcode 1590 Make Sum Divisible by P

Problem statement

https://leetcode.com/problems/make-sum-divisible-by-p/

Solution

The idea is to use cumulative sums. We will keep in last the last index for cumulative sum being equal to specific number. Then when we meet cumulative sum num, we are looking for the last place of num - k before, where k = sum(nums) % p.

Complexity

Time complexity is O(n), space is O(min(n, p)).

Code

class Solution:
    def minSubarray(self, nums, p):
        k, n = sum(nums) % p, len(nums)
        ans, last = n, {0: -1}
        if k == 0: return 0
        for i, num in enumerate(accumulate(nums)):
            if (num - k) % p in last:
                ans = min(ans, i - last[(num - k)%p])
            last[num % p] = i

        return ans if ans != n else -1