Coding · Hashing
Make Sum Divisible by P
- Reported once
- Medium
- Intern
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
Given an array of positive integers nums and an integer p, remove the shortest contiguous subarray (it may be empty, but it cannot be the whole array) so that the sum of the remaining elements is divisible by p. Return the length of the removed subarray, or -1 if no valid removal exists. For nums = [3,1,4,2] and p = 6 the answer is 1, by removing [4]. The array can hold 100,000 numbers, each up to 1,000,000,000.
Restated in our own words, not a quote from Razorpay or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: are the numbers all positive, so no negative remainders sneak in? Can p be 1? Is removing nothing allowed when the sum already works? Is removing the entire array allowed (the prompt says no)? Do I return the length or the indices? How large can the sum get?
I would assume positive numbers, p of at least 1, an answer of 0 when the whole sum is already divisible, -1 when only the whole array would work, and that I return just the length. Since the sum can reach about 10^14, I will work with remainders so numbers never grow.
Brute force
Say the obvious answer and why it is too slow.
Try every subarray as the one to remove. Build a prefix-sum array, then for each pair of ends (i, j) compute the remaining sum as the total minus the part between them, and test whether it is divisible by p. Keep the shortest valid length.
With prefix sums each test is O(1), but there are about n² / 2 pairs. For n = 100,000 that is roughly five billion checks, too slow for a normal time limit. Without prefix sums, re-adding each remaining part would be O(n³), which is hopeless. The waste is that for a fixed right end we scan every left end, even though only left ends with one specific remainder can possibly work.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n²)
- Time
- O(n) on average
- Space
- O(min(n, p))
First reduce the problem. Let total be the sum of all numbers mod p. If total is 0, remove nothing. Otherwise the remaining sum is divisible by p exactly when the removed part has a sum with remainder equal to total. So I am looking for the shortest subarray whose sum mod p equals total.
That is the prefix sum plus hash map pattern, only in modular arithmetic. The sum of the subarray after index i up to index j is prefix[j] - prefix[i]. I need that to be congruent to total, which means prefix[i] mod p must equal (prefix[j] - total) mod p. So I scan j from left to right, keep a map from each prefix remainder to the latest index where it appeared, and for each j look up the one remainder I need. If it is in the map, the subarray between has the right sum.
Why the latest index: for a fixed j, every earlier index with that remainder gives a valid subarray, and the later the start the shorter the subarray, so the most recent one is optimal. Overwriting the map entry as I go keeps exactly that. The empty prefix has remainder 0 at index -1, so I seed the map with it; this lets a removal start at index 0.
The one JavaScript trap is that % can return a negative number, so I compute (prefix - total + p) % p. Map lookups are O(1) on average, which makes the scan linear on average. Explained aloud: it is the subarray-sum-equals-k trick, with k replaced by a remainder.
Walk it through
A dry run on the example, step by step.
| i | nums[i] | prefix % 6 | Need (index) | Map after | Best |
|---|---|---|---|---|---|
| start | - | 0 | - | 0:-1 | none |
| 0 | 3 | 3 | 5 (miss) | 0:-1 3:0 | none |
| 1 | 1 | 4 | 0 (at -1) | 0:-1 3:0 4:1 | 2 |
| 2 | 4 | 2 | 4 (at 1) | 0:-1 3:0 4:1 2:2 | 1 |
| 3 | 2 | 4 | 0 (at -1) | 0:-1 3:0 4:3 2:2 | 1 |
Take nums = [3,1,4,2] and p = 6. The total is 10, and 10 mod 6 = 4, so I need the shortest subarray whose sum has remainder 4. The map starts with remainder 0 at index -1.
Index 0: the prefix remainder is 3, I need (3 - 4 + 6) mod 6 = 5, which is not in the map, so no candidate; store 3 at index 0. Index 1: prefix 4, need 0, found at -1, so length 2 (that is [3,1], sum 4); store 4 at index 1. Index 2: prefix 2, need 4, found at index 1, so length 1 (that is [4]); best becomes 1. Index 3: prefix 4, need 0, found at -1, length 4. The best stays 1, and the table shows each step.
The code
Runnable JavaScript, checked against test cases.
function minSubarray(nums, p) {
let total = 0;
for (const value of nums) total = (total + value) % p;
if (total === 0) return 0;
const lastIndexOfRemainder = new Map([[0, -1]]);
let prefix = 0;
let shortest = nums.length;
for (let i = 0; i < nums.length; i++) {
prefix = (prefix + nums[i]) % p;
const needed = (prefix - total + p) % p;
if (lastIndexOfRemainder.has(needed)) {
shortest = Math.min(shortest, i - lastIndexOfRemainder.get(needed));
}
lastIndexOfRemainder.set(prefix, i);
}
return shortest === nums.length ? -1 : shortest;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
Total already divisible (including p equal to 1, and an empty array): the early return gives 0. A single element that is not divisible, such as [5] with p = 3: the only match is the whole array, so the best length stays equal to n and the code returns -1.
Matching the whole array is the one thing the problem forbids. The scan can find it only when the prefix at the end matches the empty prefix, giving length n, and the final check turns any length n into -1. A removal that starts at index 0 works because of the seeded entry at -1; a removal at the end works because the scan covers the last index.
Duplicates in the array are harmless: the map keeps the latest index for each remainder. Large values: the running prefix is reduced mod p at every step, so it stays below p and never loses precision.
Follow-ups to expect
Where the interviewer pushes next.
- How would the code change if nums could contain negative numbers?
- How do you return the start and end indices of the removed subarray instead of its length?
- What changes if you want the longest subarray whose sum is divisible by p?
- Why does a sliding window not work for this problem?
- How would you count the subarrays whose sum is divisible by p, rather than find the shortest?
Where candidates slip
The mistakes this problem punishes.
Forgetting that JavaScript's % keeps the sign of the left operand, so (prefix - total) % p can be negative and never match a key. Add p before taking the remainder.
Other slips: skipping the seed for the empty prefix, which loses every removal that starts at index 0; storing the first index of a remainder instead of the latest, which finds longer removals; returning n instead of -1 when the only match is the whole array; and forgetting the early exit for a total of 0, which makes the lookup need remainder equal to the prefix itself and can return a wrong positive length. Summing without reducing mod p is fine in JavaScript up to about 10^15 but breaks in languages with 32-bit integers.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.