Make Sum Divisible by P

main.md

Question

Approach

I compute total % p = target. If target == 0 I return 0 immediately. Otherwise I scan the array building a running prefix sum modulo p. At each index i with current prefix modulo cur, I need a previous prefix modulo need = (cur - target) % p so that removing the subarray after that previous index up to i removes exactly target (mod p) from the total. I keep a hashmap mp mapping prefix modulo → last index where it appeared (initialized with mp[0] = -1) and update the answer with i - mp[need] whenever need exists. After checking I record mp[cur] = i. If the minimal length equals n (removing the whole array) I return -1, otherwise I return the minimal length.

Implementation

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        n = len(nums)
        total = sum(nums)
        target = total % p
        if target == 0:
            return 0
        
        mp = {0: -1}     
        cur = 0
        ans = n 
        
        for i, v in enumerate(nums):
            cur = (cur + v) % p
            need = (cur - target) % p
            if need in mp:
                ans = min(ans, i - mp[need])
            mp[cur] = i
        
        return -1 if ans == n else ans

Complexities

• Time: O(n)
• Space: O(min(n, p))