Make Sum Divisible by P: Prefix Sums and Modular Lookups

LeetCode #1590, Make Sum Divisible by P, asks you to find the shortest subarray you can remove so the remaining elements have a sum divisible by p. It combines prefix sums, modular arithmetic, and hash map lookups into one tight loop. If you have solved problems like Subarray Sum Equals K or Subarray Sums Divisible by K, you will recognize the skeleton here, but the goal flips from counting subarrays to minimizing the one you remove.

The problem

Given an array of positive integers nums and an integer p, remove the smallest subarray (possibly empty) from nums such that the sum of the remaining elements is divisible by p. Return the length of the smallest subarray that you need to remove, or -1 if it is impossible.

A subarray is a contiguous block of elements. You are not allowed to remove the entire array.

nums = [3, 1, 4, 2], p = 6  ->  1
nums = [6, 3, 5, 2], p = 9  ->  2
nums = [1, 2, 3], p = 3     ->  0

The brute force approach

The most direct approach is to try every possible subarray, compute the sum of the remaining elements, and check divisibility. For each pair (i, j), you remove nums[i..j] and check whether (total_sum - subarray_sum) % p == 0. This requires O(n^2) pairs and O(1) per check if you precompute prefix sums, giving O(n^2) time overall. That is too slow for the constraint of n up to 10^5.

The key insight

Start with the total sum of the array. Compute target = total_sum % p. If target is 0, the sum is already divisible, so return 0. Otherwise, you need to find the shortest subarray whose sum is congruent to target mod p. Removing that subarray will make the remaining sum divisible by p.

The subarray sum from index i+1 to j equals prefix[j] - prefix[i]. You want (prefix[j] - prefix[i]) % p == target, which rearranges to prefix[i] % p == (prefix[j] - target + p) % p. So at each position j, you compute the remainder you need and look it up in a hash map that stores the most recent index where each remainder appeared. "Most recent" is critical because you want the shortest subarray, which means the closest i to j.

Step-by-step walkthrough

Let us trace through nums = [3, 1, 4, 2] with p = 6. The total sum is 10, so target = 10 % 6 = 4. We need the shortest subarray whose sum mod 6 equals 4.

The code

def minSubarray(nums, p):
    total = sum(nums)
    target = total % p
    if target == 0:
        return 0

    last_seen = {0: 0}
    prefix = 0
    best = len(nums)
    n = len(nums)

    for i in range(n):
        prefix += nums[i]
        remainder = prefix % p
        need = (remainder - target + p) % p
        if need in last_seen:
            best = min(best, (i + 1) - last_seen[need])
        last_seen[remainder] = i + 1

    return best if best < n else -1

Here is how the code works:

1. Compute target. Take total_sum % p. If it is 0, the sum is already divisible, so return 0 immediately.

2. Seed the map with {0: 0}. Before processing any element, the prefix sum is 0 with remainder 0 at position 0. This lets you match subarrays that start from the beginning of the array.

3. Iterate and accumulate. For each element, add it to the running prefix sum and compute remainder = prefix % p.

4. Compute need. The value (remainder - target + p) % p tells you what remainder a previous prefix sum must have so that the subarray between them has a sum congruent to target mod p.

5. Look up need in the map. If it exists, the subarray from last_seen[need] to the current position has the right sum. Compute its length and update best if it is shorter.

6. Update the map. Store the current remainder with the current prefix index. If this remainder was seen before, overwriting is correct because you always want the most recent occurrence (shortest subarray).

7. Return the answer. If best is still equal to n, you would have to remove the entire array, which is not allowed. Return -1 in that case.

Complexity analysis

Time: O(n). You iterate through the array once. Each hash map lookup and insertion is O(1) on average, so the total work is linear.

Space: O(min(n, p)). The hash map stores one entry per distinct remainder. There are at most p distinct remainders (0 through p-1). If n is smaller than p, you store at most n + 1 entries.

The building blocks

Prefix sum with target remainder

target = total % p
need = (remainder - target + p) % p

This is the core rearrangement. Instead of checking every pair of prefix sums, you compute what remainder you need and look it up in O(1). The formula (remainder - target + p) % p is the modular equivalent of prefix[j] - prefix[i] == target from the exact-sum version of this pattern. Once you internalize this translation, you can adapt prefix sum solutions to any divisibility condition.

Last-seen index map

if need in last_seen:
    best = min(best, (i + 1) - last_seen[need])
last_seen[remainder] = i + 1

The map stores the most recent index for each remainder, not a frequency count. This is the key difference from Subarray Sums Divisible by K (which counts all valid subarrays) and from Continuous Subarray Sum (which stores the first index). Here, "most recent" minimizes the subarray length because you want the gap between j and i to be as small as possible.

Edge cases

• Sum already divisible. If total % p == 0, the answer is 0. No removal needed.
• Single element. For nums = [1] and p = 1, the total is 1, target = 0, so return 0. For nums = [1] and p = 2, target = 1, and removing the only element means removing the entire array. Return -1.
• No valid subarray. If no subarray sum has the right remainder, best stays at n and you return -1. This can happen when p is larger than the total sum and the remainder cannot be matched.
• Entire array is the only match. If the only matching subarray is the entire array, the length equals n. The check best < n catches this and returns -1.
• Multiple valid subarrays. The map always stores the most recent index, so you automatically get the shortest candidate at each step without extra work.
• Large values. Elements can be up to 10^9, but prefix sums are taken mod p, so overflow is not a concern in Python. In languages with fixed-width integers, accumulate the prefix sum as a 64-bit integer.

From understanding to recall

This problem sits at the intersection of three patterns: prefix sums, modular arithmetic, and hash map lookups. Each piece is simple on its own. The challenge is combining them fluently. You need to remember that the map stores indices (not counts), that you want the most recent occurrence (not the first), and that you need to exclude the case where the subarray covers the entire array.

Spaced repetition helps you internalize these distinctions. After a few review cycles, the formula (remainder - target + p) % p will feel as natural as prefix[j] - prefix[i] == k. You will stop confusing "last seen" maps with "first seen" maps and "frequency" maps. That precision is what makes the difference in an interview when you have 20 minutes and no room for second-guessing.

Related posts

• Subarray Sum Equals K - Same prefix sum + hash map skeleton, but looking for exact sums instead of remainders
• Subarray Sums Divisible by K - Uses the same modular arithmetic approach, but counts all valid subarrays instead of minimizing one
• Continuous Subarray Sum - Also uses prefix sums mod k, but stores the first index (not the last) to detect existence