1590. Make Sum Divisible by P - Explanation

Problem Link

1. Brute Force

Intuition

We need to find the shortest subarray to remove so that the remaining elements sum to a multiple of p. The brute force approach tries every possible subarray length starting from 1. For each length, we slide a window across the array and check if removing that window leaves a sum divisible by p. We return the first (smallest) length l that works.

Algorithm

1. Compute the total sum of the array. If it is already divisible by p, return 0.
2. For each possible subarray length l from 1 to n - 1:
   • Use a sliding window to compute the sum of each subarray of length l.
   • For each window position, calculate the remaining sum (total minus window sum).
   • If the remaining sum is divisible by p, return l.
3. If no valid subarray is found, return -1.

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        n = len(nums)
        totSum = sum(nums)

        if totSum % p == 0:
            return 0

        for l in range(1, n):
            curSum = 0
            for i in range(n):
                curSum += nums[i]
                if i >= l:
                    curSum -= nums[i - l]

                remainSum = totSum - curSum
                if remainSum % p == 0:
                    return l

        return -1

Time & Space Complexity

• Time complexity: $O(n ^ 2)$
• Space complexity: $O(1)$

---

2. Prefix Sum

Intuition

If the total sum has remainder r when divided by p, we need to remove a subarray whose sum also has remainder r (mod p). This transforms the problem into finding the shortest subarray with a specific remainder. Using prefix sums, if the current prefix has remainder curSum, we look for an earlier prefix with remainder (curSum - r + p) % p. A hash map stores the most recent index for each remainder, allowing O(1) lookups.

Algorithm

1. Calculate the total sum and its remainder remain when divided by p. If remain is 0, return 0.
2. Initialize a hash map with {0: -1} to handle subarrays starting from index 0.
3. Iterate through the array, maintaining the running prefix sum modulo p.
4. For each position, compute the target prefix remainder: (curSum - remain + p) % p.
5. If this target exists in the map, update the minimum length.
6. Store the current prefix remainder and its index in the map.
7. Return the minimum length found, or -1 if no valid subarray exists (or if removing it would leave an empty array).

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        total = sum(nums)
        remain = total % p
        if remain == 0:
            return 0

        res = len(nums)
        cur_sum = 0
        remain_to_idx = {0: -1}

        for i, n in enumerate(nums):
            cur_sum = (cur_sum + n) % p
            prefix = (cur_sum - remain + p) % p
            if prefix in remain_to_idx:
                length = i - remain_to_idx[prefix]
                res = min(res, length)
            remain_to_idx[cur_sum] = i

        return -1 if res == len(nums) else res

Time & Space Complexity

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

---

Common Pitfalls

Forgetting to Handle Negative Modulo Results

When computing (curSum - remain) % p, the result can be negative in many programming languages. Always add p before taking modulo: (curSum - remain + p) % p. Failing to do this causes incorrect hash map lookups and wrong answers.

Not Initializing the Hash Map with {0: -1}

The hash map must start with {0: -1} to handle subarrays that start from index 0. Without this initialization, you cannot detect valid subarrays that begin at the first element of the array.

Returning the Wrong Value When No Valid Subarray Exists

If the minimum length found equals n (the entire array), you must return -1 because removing all elements leaves an empty array, which is invalid. A common mistake is forgetting this edge case and returning n instead.