Watch 10 video solutions for Make Sum Divisible by P, a medium level problem involving Array, Hash Table, Prefix Sum. This walkthrough by codestorywithMIK has 24,214 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 109Problem 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 | 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 |