Make Sum Divisible by P

medium array hash map prefix sum

Problem

Remove the shortest contiguous subarray (possibly empty, but not the entire array) so the rest of nums has a sum divisible by p. Return its length, or -1 if impossible.

Inputnums=[3,1,4,2], p=6

Output1

Sum=10; 10 mod 6=4. Remove [4] (length 1).

nums

def min_subarray(nums, p):
    target = sum(nums) % p
    if target == 0: return 0
    seen = {0: -1}
    cur, ans = 0, len(nums)
    for i, x in enumerate(nums):
        cur = (cur + x) % p
        want = (cur - target) % p
        if want in seen: ans = min(ans, i - seen[want])
        seen[cur] = i
    return ans if ans < len(nums) else -1

function minSubarray(nums, p) {
  const total = nums.reduce((a, b) => a + b, 0);
  const target = total % p;
  if (target === 0) return 0;
  const seen = new Map(); seen.set(0, -1);
  let cur = 0, ans = nums.length;
  for (let i = 0; i < nums.length; i++) {
    cur = (cur + nums[i]) % p;
    const want = ((cur - target) % p + p) % p;
    if (seen.has(want)) ans = Math.min(ans, i - seen.get(want));
    seen.set(cur, i);
  }
  return ans < nums.length ? ans : -1;
}

class Solution {
    public int minSubarray(int[] nums, int p) {
        long total = 0; for (int x : nums) total += x;
        int target = (int)(total % p);
        if (target == 0) return 0;
        Map seen = new HashMap<>(); seen.put(0L, -1);
        long cur = 0; int ans = nums.length;
        for (int i = 0; i < nums.length; i++) {
            cur = (cur + nums[i]) % p;
            long want = ((cur - target) % p + p) % p;
            if (seen.containsKey(want)) ans = Math.min(ans, i - seen.get(want));
            seen.put(cur, i);
        }
        return ans < nums.length ? ans : -1;
    }
}

int minSubarray(vector& nums, int p) {
    long long total = 0; for (int x : nums) total += x;
    int target = total % p;
    if (target == 0) return 0;
    unordered_map seen; seen[0] = -1;
    long long cur = 0; int ans = nums.size();
    for (int i = 0; i < (int)nums.size(); i++) {
        cur = (cur + nums[i]) % p;
        long long want = ((cur - target) % p + p) % p;
        if (seen.count(want)) ans = min(ans, i - seen[want]);
        seen[cur] = i;
    }
    return ans < (int)nums.size() ? ans : -1;
}

Explanation

First figure out what we actually need to remove. If the whole array sums to something with remainder target = total % p, then to make the rest divisible by p we must remove a chunk whose own sum has that same remainder target. If target is already 0, nothing needs removing and the answer is 0.

We then look for the shortest contiguous chunk with that remainder using a prefix sum taken modulo p. As we sweep, cur is the running prefix mod p. A chunk ending at i and starting after some earlier index j has remainder cur minus the prefix at j.

For that chunk's remainder to equal target, the earlier prefix must equal want = (cur - target) % p. The seen map stores the latest index for each prefix mod value, so if want is in the map we get a candidate length i - seen[want] and keep the smallest.

Example: nums = [3,1,4,2], p = 6. Total is 10, so target = 4. At index 2 the running prefix mod is 8 % 6 = 2, and we look for want = (2 - 4) mod 6 = 4... ultimately the best removable chunk is just [4], length 1.

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