Make Sum Divisible by P — Prefix Mod + HashMap

Problem 187 · Make Sum Divisible by P

Difficulty: Medium · Pattern: Prefix Mod + HashMap

Remove the smallest subarray so the rest of the array sum is divisible by p.

Intuition

If total sum mod p = r, we need a subarray with sum ≡ r (mod p). Track prefix sums mod p; for each prefix cur, look for a previous prefix cur - r (mod p) in a map storing the latest index.

Solutions

// C++
int minSubarray(vector<int>& nums, int p) {
    int r = 0;
    for (int x : nums) r = (r + x) % p;
    if (r == 0) return 0;
    unordered_map<int,int> last;
    last[0] = -1;
    int cur = 0, ans = nums.size();
    for (int i = 0; i < (int)nums.size(); i++) {
        cur = (cur + nums[i]) % p;
        int need = (cur - r + p) % p;
        if (last.count(need))
            ans = min(ans, i - last[need]);
        last[cur] = i;
    }
    return ans == (int)nums.size() ? -1 : ans;
}

// Java
public int minSubarray(int[] nums, int p) {
    int r = 0;
    for (int x : nums) r = (r + x) % p;
    if (r == 0) return 0;
    Map<Integer,Integer> last = new HashMap<>();
    last.put(0, -1);
    int cur = 0, ans = nums.length;
    for (int i = 0; i < nums.length; i++) {
        cur = (cur + nums[i]) % p;
        int need = (cur - r + p) % p;
        if (last.containsKey(need))
            ans = Math.min(ans, i - last.get(need));
        last.put(cur, i);
    }
    return ans == nums.length ? -1 : ans;
}

# Python
def minSubarray(nums, p):
    r = sum(nums) % p
    if r == 0: return 0
    last = {0: -1}
    cur = 0; ans = len(nums)
    for i, x in enumerate(nums):
        cur = (cur + x) % p
        need = (cur - r) % p
        if need in last:
            ans = min(ans, i - last[need])
        last[cur] = i
    return -1 if ans == len(nums) else ans

Complexity

Time: O(n)
Space: O(n)