Make Sum Divisible by P — Solution in Python, Java & C++
Make Sum Divisible by P solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Make Sum Divisible by P is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array of positive integers nums and an integer p, remove the smallest contiguous subarray (possibly empty) so that the sum of the remaining elements is divisible by p. You may not remove the whole array.
Return the length of the subarray to remove, or -1 if it cannot be done.
Example 1
Input: nums = [3,2,4], p = 6
Output: 1
Explanation: The total is 9; removing `[3]` leaves 6.
Example 2
Input: nums = [1,2,3], p = 7
Output: -1
Explanation: The total is 6, and no proper subarray has a sum of 6 modulo 7.
Example 3
Input: nums = [5,3,6,2], p = 4
Output: 0
Explanation: The total 16 is already divisible by 4.
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^91 <= p <= 10^9
Hints for Make Sum Divisible by P
Hint 1
Let
need = sum(nums) % p. You must remove a subarray whose sum is congruent toneedmodulop.Hint 2
With prefix sums mod
p, a subarray(l, r]has sumneed(mod p) whenprefix[l] == (prefix[r] - need) mod p.Hint 3
Sweep
rfrom left to right, remembering the latest index at which each prefix remainder occurred; the latest one gives the shortest subarray ending atr.
How to solve Make Sum Divisible by P
Removing a subarray fixes the total exactly when the subarray's sum leaves the same remainder as the whole array — a prefix-sum-plus-hash-map search for the shortest such subarray.
Approach
- Compute
need = total % p. If it is 0, return 0. - Store
last[0] = -1(the empty prefix). - For each index
i, update the running prefixcur = (cur + nums[i]) % pand look upwant = (cur - need + p) % p. - If
wantwas seen at indexj, the subarrayj+1..iworks; recordi - jif shorter. Then setlast[cur] = i. - If the best length equals
n(the whole array) or nothing was found, return -1.
Why it works
The remaining sum is total - sum(sub), divisible by p iff sum(sub) ≡ need (mod p). For a subarray ending at i, that means its starting prefix remainder is want; the latest such prefix yields the shortest candidate, and overwriting last[cur] keeps exactly that.
Complexity
- Time —
O(n) - Space —
O(min(n, p))
Pitfalls
- The total can reach 10^14 — reduce modulo
pwhile summing (or use 64-bit integers). - In languages where
%keeps the sign of the dividend, addpbefore taking(cur - need) % p. - Removing the whole array is forbidden, so a best length of
nmeans -1.
Reference solution
Python
from typing import List
def minSubarray(nums: List[int], p: int) -> int:
need = sum(nums) % p
if need == 0:
return 0
last = {0: -1}
cur = 0
n = len(nums)
best = n
for i, v in enumerate(nums):
cur = (cur + v) % p
want = (cur - need) % p
if want in last:
best = min(best, i - last[want])
last[cur] = i
return -1 if best == n else bestJava
public static int minSubarray(int[] nums, int p) {
int n = nums.length;
long need = 0;
for (int v : nums) need = (need + v) % p;
if (need == 0) return 0;
Map<Long, Integer> last = new HashMap<>();
last.put(0L, -1);
long cur = 0;
int best = n;
for (int i = 0; i < n; i++) {
cur = (cur + nums[i]) % p;
long want = (cur - need + p) % p;
Integer j = last.get(want);
if (j != null) best = Math.min(best, i - j);
last.put(cur, i);
}
return best == n ? -1 : best;
}C++
int minSubarray(vector<int>& nums, int p) {
int n = nums.size();
long long need = 0;
for (int v : nums) need = (need + v) % 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 ? -1 : best;
}JavaScript
var minSubarray = function(nums, p) {
var n = nums.length;
var need = 0;
for (var i = 0; i < n; i++) need = (need + nums[i]) % p;
if (need === 0) return 0;
var last = new Map();
last.set(0, -1);
var cur = 0, best = n;
for (var j = 0; j < n; j++) {
cur = (cur + nums[j]) % p;
var want = (cur - need + p) % p;
if (last.has(want)) best = Math.min(best, j - last.get(want));
last.set(cur, j);
}
return best === n ? -1 : best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets