Make Sum Divisible by P solution and explanation
Google
9 more videos on this problem
Make Sum Divisible by P | Simplest Explanation | Full Dry Run | Leetcode 1590 | codestorywithMIKcodestorywithMIK · 27:26 · 25K views
Make Sum Divisible by P - Leetcode 1590 - PythonNeetCodeIO · 15:00 · 22K views
Make Sum Divisible by P - Leetcode 1590 - PythonNeetCodeIO · 15:00 · 14K views
Make Sum Divisible by P | Leetcode 1590Techdose · 22:55 · 5K views
Make Sum Divisible by P | LeetCode 1590 | C++ | PythonClashing Coder · 27:15 · 5K views
1590. Make Sum Divisible by P (Leetcode Medium)Programming Live with Larry · 21:42 · 2K views
Make Sum Divisible by P | LeetCode 1590 | Complete Intuition ExplainedSanyam IIT Guwahati · 24:23 · 1K views
Daily Leetcode #2070: Nov 30, 2025 - 1590. Make Sum Divisible by PProgramming Live with Larry · 12:24 · 718 views
Make Sum Divisible by P | LeetCode 1590 - Pythonimpoldev · 17:13 · 219 views
Make Sum Divisible by P | Leetcode 1590 | Prefix Sum Modulo | Java Code | Developer CoderDeveloper Coder · 27:40 · 163 views
The problem
Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.
Return the length of the smallest subarray that you need to remove, or -1 if it's impossible.
A subarray is defined as a contiguous block of elements in the array.
Example 1:
Input: nums = [3,1,4,2], p = 6 Output: 1 Explanation: The sum of the elements in nums is 10, which is not divisible by 6. We can remove the subarray [4], and the sum of the remaining elements is 6, which is divisible by 6.
Example 2:
Input: nums = [6,3,5,2], p = 9 Output: 2 Explanation: We cannot remove a single element to get a sum divisible by 9. The best way is to remove the subarray [5,2], leaving us with [6,3] with sum 9.
Example 3:
Input: nums = [1,2,3], p = 3 Output: 0 Explanation: Here the sum is 6. which is already divisible by 3. Thus we do not need to remove anything.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= p <= 109
Approach overview
Problem Overview: You are given an integer array nums and an integer p. Remove the smallest contiguous subarray so that the sum of the remaining elements becomes divisible by p. The removed subarray cannot be the entire array.
The key observation: if the total array sum has remainder r = total % p, you must remove a subarray whose sum also has remainder r. The task becomes finding the shortest subarray with that remainder.
Approach 1: Brute Force Subarray Search (O(n²) time, O(1) space)
Check every possible subarray and compute its sum. For each candidate, subtract its sum from the total and verify whether the remaining sum becomes divisible by p. This requires nested loops over the array and repeated modulo checks. While simple to implement, it performs poorly for large inputs because there are O(n²) possible subarrays. Useful only for understanding the problem or verifying small cases.
Approach 2: Prefix Sum and Remainder with HashMap (O(n) time, O(n) space)
Compute prefix sums while tracking each prefix remainder modulo p. Let target = total_sum % p. While iterating, maintain prefix % p and look for a previous prefix remainder that satisfies (current - target) % p. A hash table maps each remainder to its most recent index, allowing constant-time lookup. This transforms the search for a valid removable subarray into a prefix remainder matching problem using prefix sums. The result is the minimum length between matching indices.
The insight: if two prefix sums differ by remainder target modulo p, the subarray between them has exactly the remainder needed to remove.
Approach 3: Sliding Window with Two Pointers (O(n) time, O(1) space)
A two-pointer technique can be applied when reasoning about subarray sums incrementally. Expand the right pointer to accumulate a running sum and shrink from the left when conditions exceed the required remainder window. This approach tries to maintain a candidate window whose sum modulo p matches the required remainder. It avoids extra memory and relies on pointer movement over the array. While less common than the prefix-hash solution, it works when the window behavior can be controlled with modular checks.
Recommended for interviews: The Prefix Sum + HashMap approach is what interviewers expect. It reduces a seemingly complex removal problem into a modular prefix lookup and runs in linear time. Brute force shows you understand the condition, but the prefix remainder trick demonstrates algorithmic maturity.
Approach 1: Prefix Sum and Remainder with HashMap
This approach involves first calculating the remainder of the sum of the given array with respect to p. By maintaining a prefix sum and using the properties of modular arithmetic, we can determine the shortest subarray whose removal results in a remainder of zero.
def min_subarray(nums, p):
total_mod = sum(nums) % p
if total_mod == 0:
return 0
prefix_sum = 0
prefix_map = {0: -1}
min_len = len(nums)
for i, num in enumerate(nums):
prefix_sum = (prefix_sum + num) % p
target = (prefix_sum - total_mod) % p
if target in prefix_map:
min_len = min(min_len, i - prefix_map[target])
prefix_map[prefix_sum] = i
return min_len if min_len != len(nums) else -1#include <vector>
#include <unordered_map>
#include <numeric>
using namespace std;
int minSubarray(vector<int>& nums, int p) {
int total_mod = accumulate(nums.begin(), nums.end(), 0) % p;
if (total_mod == 0) return 0;
unordered_map<int, int> prefix_map;
prefix_map[0] = -1;
int prefix_sum = 0, min_len = nums.size();
for (int i = 0; i < nums.size(); ++i) {
prefix_sum = (prefix_sum + nums[i]) % p;
int target = (prefix_sum - total_mod + p) % p;
if (prefix_map.find(target) != prefix_map.end()) {
min_len = min(min_len, i - prefix_map[target]);
}
prefix_map[prefix_sum] = i;
}
return min_len == nums.size() ? -1 : min_len;
}This implementation calculates the prefix sum and stores remainders in a hashmap. By checking if the target remainder exists in the hashmap, we find the minimal subarray that aligns with our requirement. We update the hashmap with current prefix sums iteratively.
Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(n), for storing prefix sums in the hashmap.
Approach 2: Sliding Window with Two Pointers
This approach makes use of a sliding window or two-pointer technique to identify the minimal subarray which upon removal makes the sum of the remaining elements divisible by p.
import java.util.*;
public class Solution {
public int minSubarray(int[] nums, int p) {
int totalMod = Arrays.stream(nums).reduce(0, Integer::sum) % p;
if (totalMod == 0) return 0;
Map<Integer, Integer> prefixMap = new HashMap<>();
prefixMap.put(0, -1);
int prefixSum = 0, minLen = nums.length;
for (int i = 0; i < nums.length; i++) {
prefixSum = (prefixSum + nums[i]) % p;
int target = (prefixSum - totalMod + p) % p;
if (prefixMap.containsKey(target)) {
minLen = Math.min(minLen, i - prefixMap.get(target));
}
prefixMap.put(prefixSum, i);
}
return minLen == nums.length ? -1 : minLen;
}
}function minSubarray(nums, p) {
let totalMod = nums.reduce((a, b) => a + b, 0) % p;
if (totalMod === 0) return 0;
let prefixMap = {0: -1};
let prefixSum = 0, minLen = nums.length;
for (let i = 0; i < nums.length; i++) {
prefixSum = (prefixSum + nums[i]) % p;
let target = (prefixSum - totalMod + p) % p;
if (prefixMap.hasOwnProperty(target)) {
minLen = Math.min(minLen, i - prefixMap[target]);
}
prefixMap[prefixSum] = i;
}
return minLen === nums.length ? -1 : minLen;
}The Java solution uses a HashMap to keep track of prefix sums as keys, linked to their indexes. The final loop computes prefix sums iteratively and checks for the desired remainder, computing the minimal subarray, if applicable.
Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(n), for maintaining the hashmap.
Approach 3: Prefix Sum + Hash Table
First, we calculate the sum of all elements in the array nums modulo p, denoted as k. If k is 0, it means the sum of all elements in the array nums is a multiple of p, so we directly return 0.
If k is not 0, we need to find the shortest subarray such that removing this subarray makes the sum of the remaining elements modulo p equal to 0.
We can traverse the array nums, maintaining the current prefix sum modulo p, denoted as cur. We use a hash table last to record the last occurrence of each prefix sum modulo p.
If there exists a subarray ending at nums[i] such that removing this subarray makes the sum of the remaining elements modulo p equal to 0, we need to find a previous prefix sum modulo p equal to target at position j such that (target + k - cur) bmod p = 0. If found, we can remove the subarray nums[j+1,..i] to make the sum of the remaining elements modulo p equal to 0.
Therefore, if there exists a target = (cur - k + p) bmod p, we can update the answer to min(ans, i - j). Then, we update last[cur] to i. We continue traversing the array nums until the end to get the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
function minSubarray(nums: number[], p: number): number {
let k = 0;
for (const x of nums) {
k = (k + x) % p;
}
if (k === 0) {
return 0;
}
const last = new Map<number, number>();
last.set(0, -1);
const n = nums.length;
let ans = n;
let cur = 0;
for (let i = 0; i < n; ++i) {
cur = (cur + nums[i]) % p;
const target = (cur - k + p) % p;
if (last.has(target)) {
const j = last.get(target)!;
ans = Math.min(ans, i - j);
}
last.set(cur, i);
}
return ans === n ? -1 : ans;
}func minSubarray(nums []int, p int) int {
k := 0
for _, x := range nums {
k = (k + x) % p
}
if k == 0 {
return 0
}
last := map[int]int{0: -1}
n := len(nums)
ans := n
cur := 0
for i, x := range nums {
cur = (cur + x) % p
target := (cur - k + p) % p
if j, ok := last[target]; ok {
ans = min(ans, i-j)
}
last[cur] = i
}
if ans == n {
return -1
}
return ans
}use std::collections::HashMap;
impl Solution {
pub fn min_subarray(nums: Vec<i32>, p: i32) -> i32 {
let mut k = 0;
for &x in &nums {
k = (k + x) % p;
}
if k == 0 {
return 0;
}
let mut last = HashMap::new();
last.insert(0, -1);
let n = nums.len();
let mut ans = n as i32;
let mut cur = 0;
for i in 0..n {
cur = (cur + nums[i]) % p;
let target = (cur - k + p) % p;
if let Some(&prev_idx) = last.get(&target) {
ans = ans.min(i as i32 - prev_idx);
}
last.insert(cur, i as i32);
}
if ans == n as i32 {
-1
} else {
ans
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix Sum and Remainder with HashMap | Time Complexity: O(n), where n is the length of nums. |
| Sliding Window with Two Pointers | Time Complexity: O(n), where n is the length of nums. |
| Prefix Sum + Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Check | O(n^2) | O(1) | Small arrays or when explaining the basic idea before optimization |
| Prefix Sum + HashMap | O(n) | O(n) | General case and interview-preferred optimal solution |
| Sliding Window Two Pointers | O(n) | O(1) | When minimizing extra memory and reasoning with window-based sums |
Frequently asked questions
Is Make Sum Divisible by P easy or hard?
Make Sum Divisible by P is rated Medium difficulty on LeetCode with an acceptance rate around 40%. The challenge comes from recognizing the modular prefix sum pattern rather than brute-force checking all subarrays.
Make Sum Divisible by P Python/Java solution
Most implementations use the prefix sum + hash map technique. Python solutions typically use a dictionary for remainder lookup, while Java uses a HashMap. Both versions iterate once through the array and maintain prefix modulo values to compute the minimum subarray length.
How to solve Make Sum Divisible by P in O(n)?
First compute total_sum % p. If the remainder is r, you need to remove a subarray whose sum % p equals r. While scanning the array, maintain prefix_sum % p and store previous remainders in a hash map. For each index, check if (current_remainder - r + p) % p exists in the map to get the shortest valid subarray.
What is the best approach for Make Sum Divisible by P?
The best approach uses prefix sums with a hash map to track remainders modulo p. Compute the total remainder and search for the shortest subarray whose remainder matches it. This method runs in O(n) time with O(n) extra space and efficiently finds the minimum removable subarray.
Is Make Sum Divisible by P asked at Google/Amazon/Meta?
Variants of prefix sum with modular arithmetic frequently appear in interviews at companies like Google, Amazon, and Meta. Problems involving subarray sums, modulo operations, and hash maps are common because they test algorithmic pattern recognition and hash-based optimization.
What data structure is used in Make Sum Divisible by P?
The core data structure is a hash map that stores prefix remainder values and their indices. Combined with prefix sums, this structure allows constant-time lookup to determine whether a previous prefix can form the required removable subarray.
What is the time complexity of Make Sum Divisible by P?
The optimal solution runs in O(n) time because the array is processed once while maintaining prefix remainders in a hash map. Each step performs constant-time lookups and updates. Space complexity is O(n) due to storing remainders.