BinarySearch 0924 Delete Sublist to Make Sum Divisible By K

Problem statement

https://binarysearch.com/problems/Delete-Sublist-to-Make-Sum-Divisible-By-K/

Solution

Equal to Leetcode 1590 Make Sum Divisible by P.

Complexity

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

Code

class Solution:
    def solve(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