1590.Make Sum Divisible by P

• Link: 1590. Make Sum Divisible by P - Medium
• Track: NeetCode150

Question

Restate the problem

• Given an array nums and integer p, remove the shortest subarray such that the remaining elements’ sum is divisible by p.
• Return the length of that subarray, or -1 if impossible.
• You cannot remove the entire array.

Edge Case

• If rem == 0 (sum(nums) % p == 0), no removal needed → return 0
• If no valid subarray found → return -1

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Prefix Sum + HashMap	$O(n)$	$O(n)$

Method 1 - Prefix Sum + HashMap

Approach

Key Insight

(cur − target) % p == rem → target = (cur − rem) % p
→ look up target in table (Two Sum pattern).

Step-by-step:

Complexity

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

Code

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        rem = sum(nums) % p
        if rem == 0:
            return 0
 
        table = {0: -1}
        prefix = 0
        ans = len(nums)
 
        for i, num in enumerate(nums):
            prefix += num
            cur = prefix % p
            target = (cur - rem) % p
 
            if target in table:
                ans = min(ans, i - table[target])
 
            table[cur] = i
 
        return ans if ans < len(nums) else -1

---

Mistake

• Forgetting {0: -1} init: Without it, subarrays starting at index 0 are never found. target == 0 would have no match even when cur == rem.
• Keeping earliest index instead of latest: table[cur] = i should always overwrite. We want the most recent j so that i - j is minimized. Keeping the first occurrence makes the subarray unnecessarily long.
• Not checking ans < len(nums): Removing the entire array is not allowed. If the only valid subarray is nums[0..n-1], return -1.
• Wrong target formula: target = (cur - rem) % p, not (rem - cur) % p. In Python both work numerically due to Python’s modulo, but the logic is: we’re looking for a past prefix whose value matches cur - rem mod p.