Make Sum Divisible by P
Make Sum Divisible by P is a medium arrays & hashing problem solved with the prefix sum strategy pattern.
The best approach, optimal (prefix remainders + hash map), runs in O(n) time and O(min(n, p)) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (every subarray) up.
Problem
You are given an array of positive integers nums and an integer p. Remove the shortest contiguous subarray (possibly empty) so that the sum of the remaining elements is divisible by p. You are not allowed to remove the entire array.
Return the length of that shortest subarray, or -1 if no allowed removal makes the remaining sum divisible by p.
Examples
Example 1
- Input
nums = [4, 7, 2, 6], p = 5- Output
1- Why
- The total is 19, which leaves remainder 4. Removing [4] leaves 15, a multiple of 5.
Example 2
- Input
nums = [5, 10], p = 5- Output
0- Why
- The total 15 is already divisible by 5, so nothing has to be removed.
Example 3
- Input
nums = [2, 3], p = 7- Output
-1- Why
- The only subarray with the right remainder is the whole array, which may not be removed.
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^91 <= p <= 10^9
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (every subarray) | O(n²) | O(1) |
| Optimal (prefix remainders + hash map) | O(n) | O(min(n, p)) |
1Brute force (every subarray)
O(n²)Every (start, end) pair is visited once.O(1)Only a few counters.Compute need = total % p. Try every start index and grow the subarray to the right, keeping its sum modulo p. Whenever the remainder equals need and the subarray is not the whole array, it is a candidate.
- need = total % p; if need == 0 return 0.
- For each i, set cur = 0 and for j from i: cur = (cur + nums[j]) % p.
- If cur == need and j - i + 1 < n, update the best length.
- Return best, or -1 if nothing was found.
class Solution {
public int minSubarray(int[] nums, int p) {
int n = nums.length;
long total = 0;
for (int x : nums) total += x;
long need = total % p;
if (need == 0) return 0;
int best = n;
for (int i = 0; i < n; i++) {
long cur = 0;
for (int j = i; j < n; j++) {
cur = (cur + nums[j]) % p;
if (cur == need && j - i + 1 < best) best = j - i + 1;
}
}
return best < n ? best : -1;
}
}class Solution:
def minSubarray(self, nums: List[int], p: int) -> int:
n = len(nums)
need = sum(nums) % p
if need == 0:
return 0
best = n
for i in range(n):
cur = 0
for j in range(i, n):
cur = (cur + nums[j]) % p
if cur == need and j - i + 1 < best:
best = j - i + 1
return best if best < n else -1class Solution {
public:
int minSubarray(vector<int>& nums, int p) {
int n = nums.size();
long long total = 0;
for (int x : nums) total += x;
long long need = total % p;
if (need == 0) return 0;
int best = n;
for (int i = 0; i < n; i++) {
long long cur = 0;
for (int j = i; j < n; j++) {
cur = (cur + nums[j]) % p;
if (cur == need && j - i + 1 < best) best = j - i + 1;
}
}
return best < n ? best : -1;
}
};function minSubarray(nums, p) {
const n = nums.length;
let total = 0;
for (const x of nums) total = (total + x) % p;
const need = total;
if (need === 0) return 0;
let best = n;
for (let i = 0; i < n; i++) {
let cur = 0;
for (let j = i; j < n; j++) {
cur = (cur + nums[j]) % p;
if (cur === need && j - i + 1 < best) best = j - i + 1;
}
}
return best < n ? best : -1;
}2Optimal (prefix remainders + hash map)
O(n)One pass with O(1) hash map work per element.O(min(n, p))At most one map entry per distinct prefix remainder.If the prefix remainder at the right end is cur, the subarray ending here has remainder need exactly when the prefix just before its start had remainder (cur - need) mod p. Store the latest index of each prefix remainder; the latest one gives the shortest subarray ending at the current index.
- need = total % p; if need == 0 return 0.
- last = {0: -1}; cur = 0; best = n.
- For each i: cur = (cur + nums[i]) % p; want = (cur - need + p) % p; if want is in last, best = min(best, i - last[want]).
- Record last[cur] = i.
- Return best < n ? best : -1 (removing everything is not allowed).
class Solution {
public int minSubarray(int[] nums, int p) {
int n = nums.length;
long total = 0;
for (int x : nums) total += x;
int need = (int) (total % p);
if (need == 0) return 0;
Map<Integer, Integer> last = new HashMap<>();
last.put(0, -1);
long cur = 0;
int best = n;
for (int i = 0; i < n; i++) {
cur = (cur + nums[i]) % p;
int want = (int) ((cur - need + p) % p);
Integer at = last.get(want);
if (at != null) best = Math.min(best, i - at);
last.put((int) cur, i);
}
return best < n ? best : -1;
}
}class Solution:
def minSubarray(self, nums: List[int], p: int) -> int:
n = len(nums)
need = sum(nums) % p
if need == 0:
return 0
last = {0: -1}
cur = 0
best = n
for i, x in enumerate(nums):
cur = (cur + x) % p
want = (cur - need) % p
if want in last:
best = min(best, i - last[want])
last[cur] = i
return best if best < n else -1class Solution {
public:
int minSubarray(vector<int>& nums, int p) {
int n = nums.size();
long long total = 0;
for (int x : nums) total += x;
long long need = total % p;
if (need == 0) return 0;
unordered_map<long long, int> last;
last[0] = -1;
long long cur = 0;
int best = n;
for (int i = 0; i < n; i++) {
cur = (cur + nums[i]) % p;
long long want = (cur - need + p) % p;
auto it = last.find(want);
if (it != last.end()) best = min(best, i - it->second);
last[cur] = i;
}
return best < n ? best : -1;
}
};function minSubarray(nums, p) {
const n = nums.length;
let total = 0;
for (const x of nums) total = (total + x) % p;
const need = total;
if (need === 0) return 0;
const last = new Map();
last.set(0, -1);
let cur = 0;
let best = n;
for (let i = 0; i < n; i++) {
cur = (cur + nums[i]) % p;
const want = (cur - need + p) % p;
if (last.has(want)) best = Math.min(best, i - last.get(want));
last.set(cur, i);
}
return best < n ? best : -1;
}Edge cases to test
- The total is already divisible by p (answer 0)
- Only the whole array would work (answer -1)
- p = 1: every sum is divisible
- Large values: running sums overflow a 32-bit integer
- p larger than the total sum
Hints
Hint 1
Let need = total % p. You must remove a subarray whose sum leaves remainder need when divided by p.
Hint 2
A subarray sum is a difference of two prefix sums. Write the condition with prefix remainders: (pre[j] - pre[i]) % p == need.
Hint 3
For each right end, which prefix remainder do you need on the left? Keep the latest index of every prefix remainder in a hash map.
FAQ
What is the best time complexity for Make Sum Divisible by P?
Optimal (prefix remainders + hash map) runs in O(n) time and O(min(n, p)) extra space. One pass with O(1) hash map work per element.
Which pattern does Make Sum Divisible by P use?
It is a arrays & hashing problem that uses the prefix sum strategy pattern. Other problems with the same pattern: Subarray Sum Equals K, Subarray with given XOR, Range Sum Query - Immutable.
Is there a brute force solution for Make Sum Divisible by P?
Yes. Brute force (every subarray) takes O(n²) time and O(1) space. Compute need = total % p.
Which edge cases should I test for Make Sum Divisible by P?
The total is already divisible by p (answer 0); Only the whole array would work (answer -1); p = 1: every sum is divisible; Large values: running sums overflow a 32-bit integer; p larger than the total sum.