Make Sum Divisible by P

How it works

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.

Steps

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).

Complexity

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

Things to watch for

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.

from typing import List

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

class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        long total = 0;
        for (int num : nums) total += num;
        int remain = total % p;
        if (remain == 0) return 0;

        int res = nums.size();
        long curSum = 0;
        unordered_map<int, int> map;
        map[0] = -1;

        for (int i = 0; i < nums.size(); i++) {
            curSum = (curSum + nums[i]) % p;
            int prefix = (curSum - remain + p) % p;
            if (map.count(prefix)) {
                res = min(res, i - map[prefix]);
            }
            map[curSum] = i;
        }

        return res == nums.size() ? -1 : res;
    }
};