Make Sum Divisible by P

Make Sum Divisible by P

What is this problem about?

The Make Sum Divisible by P problem provides an array of positive integers and an integer p. Your objective is to remove the shortest possible contiguous subarray such that the sum of the remaining elements in the array is strictly divisible by p. If it's impossible, return -1. You cannot remove the entire array.

Why is this asked in interviews?

This is an advanced modular arithmetic and Hash Table problem. It is asked by top-tier companies to evaluate your mathematical reasoning. Instead of asking you to find a subarray that sums to X, it asks you to find a subarray to remove so the remainder is divisible. This tests your ability to invert a problem mathematically using the Prefix Sum modulo properties.

Algorithmic pattern used

This problem leverages Prefix Sums and a Hash Map with modular arithmetic.

1. Find the total sum of the array modulo p. Let this be rem. If rem == 0, return 0 (no removal needed).
2. We need to find a contiguous subarray whose sum modulo p is exactly rem.
3. As we iterate through the array, we calculate the running prefix sum modulo p. We use a Hash Map to store the most recent index of each prefix sum modulo.
4. We look for a previous prefix sum that satisfies: (current_prefix_sum_mod - rem + p) % p. The distance between the current index and that previous index gives the length of the subarray to remove.

Example explanation

Array [3, 1, 4, 2], p = 6. Total sum = 10. 10 % 6 = 4. So rem = 4. We must remove a subarray that sums to 4 (mod 6). Iterate and track prefix mod:

• Map initialized with {0: -1}.
• Index 0 (3): sum = 3. 3 % 6 = 3. We need (3 - 4 + 6) % 6 = 5. Not in map. Map {..., 3: 0}.
• Index 1 (1): sum = 4. 4 % 6 = 4. We need (4 - 4 + 6) % 6 = 0. It IS in the map at -1! Length to remove = 1 - (-1) = 2. Subarray is [3, 1].
• Index 2 (4): sum = 8. 8 % 6 = 2. We need (2 - 4 + 6) % 6 = 4. It IS in the map at 1! Length to remove = 2 - 1 = 1. Subarray is [4]. Minimum length found is 1 (removing just the 4 leaves 3+1+2=6, divisible by 6).

Common mistakes candidates make

The most common mistake is messing up the modulo math for negative numbers. In many programming languages (like Java and C++), a % b can be negative if a is negative. You must use the formula (current_mod - rem + p) % p to ensure the target you are looking for in the Hash Map is strictly positive. Another error is forgetting to prevent the removal of the entire array.

Interview preparation tip

For the Make Sum Divisible by P coding problem, drill the relationship between prefix sums and targets. If you need a subarray sum equal to target, you look for current_sum - target in your map. If you need it modulo p, you look for (current_mod - target_mod + p) % p. This exact modulo formula is a recurring hero in advanced array manipulation interviews.