1590. Make Sum Divisible by P
Problem Description
The task at hand is to find the shortest contiguous subarray that can be removed from a given array of positive integers nums
, such that the sum of the remaining elements is divisible by a given integer p
. The subarray to be removed can range in size from zero (meaning no elements need to be removed) to one less than the size of the array (since removing the entire array isn't allowed). If it's impossible to find such a subarray, the function should return -1.
This is a modulo-based problem dealing with the concept of remainders. When we talk about the sum of the remaining elements being divisible by p
, the sum modulo p
should be 0
(that is sum % p == 0
).
Intuition
The keyword in this problem is "divisibility by p
", which involves understanding how the modulo operation works. To arrive at the solution, we need to find a subarray such that when it's removed, the sum of the remaining elements of the array is a multiple of p
.
The intuition behind the solution lies in two key observations:
-
Prefix Sum and Modulo: Compute the cumulative sum of elements as you traverse through the array, taking the modulo with
p
at each step. This helps us detect if by removing a previous part of the sequence, we can achieve a sum that's a multiple ofp
. -
Using a Hash Map to Remember Modulo Indices: By keeping track of the indices where each modulo value is first seen in a hash map, we can quickly find out where to cut the subarray. If the current modulo value minus the target modulo value has been seen before, the segment between that index and the current index could potentially be removed to satisfy the problem's requirements.
If the sum of the entire array modulo p
is 0, no removal is needed (the result is zero subarray length). If the sum modulo p
equals k
, we need to remove a segment of the array with a sum that is equivalent to k
modulo p
. The solution uses this approach to find the minimum length subarray that satisfies the condition.
Learn more about Prefix Sum patterns.
Solution Approach
The solution approach uses a hash map (or dictionary in Python) and a prefix sum concept combined with the modulo operation. Here's how the implementation works, broken down step by step:
-
Calculation of the overall sum modulo
p
: The variablek
holds the result of total sum modulop
which helps us identify what sum value needs to be removed (if possible) to make the overall sum divisible byp
. -
If
k
is0
, nothing needs to be removed since the total sum is already divisible byp
. The solution will return0
in this case. -
Initialization of a hash map
last
with a key-value pair{0: -1}
which tracks the modulus of the prefix sum and its index. -
Loop through the array using enumerate, which gives both the index
i
and the elementx
.- Update the current prefix sum modulo
p
, store it incur
. - Compute
target
, which is the prefix sum that we need to find in thelast
hash map. This is calculated as(cur - k + p) % p
.
- Update the current prefix sum modulo
-
If the
target
is found in thelast
map, this means there exists a subarray whose sum modulop
is exactlyk
, and we could remove it to satisfy the condition. Update theans
with the minimum length found so far. -
Update the hash map
last
with the current prefix sum modulop
and its index. -
After finishing the loop, check if
ans
is still equal to the length of the array (which means no valid subarray was found) and return-1
. Otherwise, return theans
which is the length of the smallest subarray to remove.
The data structure used here is a Hash Map (or Dictionary), which allows for an efficient lookup to find whether we have previously encountered a specific prefix sum modulo p
. The algorithm is a manifestation of a sliding window where the window is dynamically adjusted based on the prefix sums and the target modulo values.
This approach efficiently solves the problem by transforming it into a scenario to find two prefix sums with the same modulo after removing the elements from between these two sums. By using the hash map, we are able to quickly find out if we've seen a prefix sum that allows us to create a valid sum divisible by p
when the subarray between two such prefix sum occurrences is removed.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's reconsider the example with the array of integers nums = [3, 1, 4, 6]
and the integer p = 5
. Our objective remains to identify the shortest contiguous subarray that, when removed, results in the sum of the remaining elements being divisible by p
.
Following the steps outlined in the solution approach:
-
We calculate the overall sum of the array, which is
3 + 1 + 4 + 6 = 14
. The modulus of this sum withp
gives us14 % 5 = 4
, which meansk = 4
. This indicates that we need to remove a subarray whose sum modulop
equals4
. -
Since
k
is not0
, we understand that some elements need to be removed. Ifk
were0
, it would imply no removal is necessary, and we could return0
. -
We initialize a hash map
last
with the entry{0: -1}
. This map is used to keep track of the indices where each modulo value of the prefix sum is first encountered. -
As we iterate through
nums
:- At index
0
with element3
,cur = 3 % 5 = 3
. We calculatetarget = (3 - 4 + 5) % 5 = 4
. Sincetarget
is not found inlast
, we proceed without any removal. - Updating
last
to{0: -1, 3: 0}
. - At index
1
with element1
,cur = (3 + 1) % 5 = 4
. We calculatetarget = (4 - 4 + 5) % 5 = 0
. Thetarget
is found inlast
, indicating a potential subarray from index-1
to1
. However, this does not provide a valid subarray for removal based on our current understanding. - Updating
last
to{0: -1, 3: 0, 4: 1}
. - At index
2
with element4
,cur = (4 + 4) % 5 = 3
. We calculatetarget = (3 - 4 + 5) % 5 = 4
, andlast
already has a4
. This again does not yield a smaller subarray than before. - The hash map
last
remains{0: -1, 3: 0, 4: 1}
. - At index
3
with element6
,cur = (3 + 6) % 5 = 4
. We calculatetarget = (4 - 4 + 5) % 5 = 0
again. Thetarget
is inlast
, suggesting a potential subarray from index-1
to3
. However, this insight needs correction.
- At index
-
Upon closer examination, we realize the mistake in our previous assessment. The correct approach is to identify the subarray
[4]
at index2
, which has a length of1
and a sum of4
, which is exactlyk
. Removing this subarray leaves us with a sum of10
, which is divisible byp=5
. -
Therefore, the corrected answer for the input
nums = [3, 1, 4, 6]
andp = 5
is1
. This indicates that the shortest subarray we can remove to make the sum of the remaining elements divisible by5
has a length of1
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def minSubarray(self, nums: List[int], p: int) -> int:
5 # Find the remainder of the sum of nums when divided by p
6 remainder = sum(nums) % p
7 # If the sum of nums is already divisible by p, the subarray length is 0
8 if remainder == 0:
9 return 0
10
11 # Hash map to store the most recent index where a particular mod value is found
12 mod_indices = {0: -1}
13 # The current prefix sum mod p
14 current_mod = 0
15 # Initialize minimum length to the length of nums array
16 min_length = len(nums)
17
18 # Iterate through the numbers in the array to find the shortest subarray
19 for index, num in enumerate(nums):
20 # Update the current mod value
21 current_mod = (current_mod + num) % p
22 # Calculate the target mod value which would balance the current mod to make a divisible sum
23 target_mod = (current_mod - remainder + p) % p
24
25 # If the target mod value is found in the mod_indices
26 if target_mod in mod_indices:
27 # Update the min_length if a shorter subarray is found
28 min_length = min(min_length, index - mod_indices[target_mod])
29 # Update the mod_indices with the current index
30 mod_indices[current_mod] = index
31
32 # If min_length hasn't been updated, the required subarray doesn't exist
33 return -1 if min_length == len(nums) else min_length
34
1class Solution {
2 public int minSubarray(int[] nums, int p) {
3 // Initialize remainder to accumulate the sum of the array elements modulo p
4 int remainder = 0;
5 for (int num : nums) {
6 remainder = (remainder + num) % p;
7 }
8
9 // If the total sum is a multiple of p, no subarray needs to be removed
10 if (remainder == 0) {
11 return 0;
12 }
13
14 // Create a hashmap to store the most recent index where a certain modulo value was seen
15 Map<Integer, Integer> lastIndex = new HashMap<>();
16 lastIndex.put(0, -1); // Initialize with the value 0 at index -1
17
18 int n = nums.length;
19 // Set the initial smallest subarray length to the array's length
20 int smallestLength = n;
21 int currentSumModP = 0; // This will keep the running sum modulo p
22
23 for (int i = 0; i < n; ++i) {
24 currentSumModP = (currentSumModP + nums[i]) % p;
25
26 // Calculate the target modulo value that would achieve our remainder if removed
27 int target = (currentSumModP - remainder + p) % p;
28
29 // If the target already exists in the hashmap, calculate the length of the subarray that could be removed
30 if (lastIndex.containsKey(target)) {
31 smallestLength = Math.min(smallestLength, i - lastIndex.get(target));
32 }
33
34 // Update the hashmap with the current modulo value and its index
35 lastIndex.put(currentSumModP, i);
36 }
37
38 // If the smallestLength was not updated, return -1 to signify no valid subarray exists
39 return smallestLength == n ? -1 : smallestLength;
40 }
41}
42
1class Solution {
2public:
3 int minSubarray(vector<int>& nums, int p) {
4 int remainder = 0; // Use 'remainder' to store the mod value of the sum of array.
5
6 // Calculate the sum of nums mod p.
7 for (int& num : nums) {
8 remainder = (remainder + num) % p;
9 }
10
11 // If the remainder is 0, the whole array satisfies the condition.
12 if (remainder == 0) {
13 return 0;
14 }
15
16 // Use a hashmap to store the most recent index where a certain mod value was seen.
17 unordered_map<int, int> modIndexMap;
18 modIndexMap[0] = -1;
19 int n = nums.size(); // The length of the nums array.
20 int minLength = n; // Initialize minLength with the maximum possible length.
21 int currentSum = 0; // Running sum of the elements.
22
23 // Iterate through the nums array.
24 for (int i = 0; i < n; ++i) {
25 currentSum = (currentSum + nums[i]) % p;
26
27 // Calculate the target mod value that could potentially reduce the running sum to a multiple of p.
28 int target = (currentSum - remainder + p) % p;
29
30 // If the target is found in the map, update the minLength with the shortest length found so far.
31 if (modIndexMap.count(target)) {
32 minLength = min(minLength, i - modIndexMap[target]);
33 }
34
35 // Update the map with the current cumulative mod value and current index.
36 modIndexMap[currentSum] = i;
37 }
38
39 // If minLength is not changed, return -1 for no such subarray, otherwise return the minLength.
40 return minLength == n ? -1 : minLength;
41 }
42};
43
1function minSubarray(nums: number[], p: number): number {
2 // Initialize a variable to store the remainder of the array sum modulo p.
3 let remainder = 0;
4 // Calculate the sum of the array elements modulo p.
5 for (const num of nums) {
6 remainder = (remainder + num) % p;
7 }
8 // If the remainder is 0, the entire array is already divisible by p, so return 0.
9 if (remainder === 0) {
10 return 0;
11 }
12 // Create a map to store the last index where a particular remainder was found.
13 const lastIndexOfRemainder = new Map<number, number>();
14 // Map the remainder 0 to the index before the start of the array.
15 lastIndexOfRemainder.set(0, -1);
16 // Get the total number of elements in the array.
17 const n = nums.length;
18 // Initialize answer as the length of the array.
19 let answer = n;
20 // Initialize a variable to store the current prefix sum modulo p.
21 let currentPrefixSum = 0;
22 // Iterate through the array to find the minimum length of subarray.
23 for (let i = 0; i < n; ++i) {
24 // Update the current prefix sum.
25 currentPrefixSum = (currentPrefixSum + nums[i]) % p;
26 // Calculate the target remainder we want to find in the map.
27 const targetRemainder = (currentPrefixSum - remainder + p) % p;
28 // Check if we have previously seen this target remainder.
29 if (lastIndexOfRemainder.has(targetRemainder)) {
30 // Get the last index where this remainder was seen.
31 const lastIndex = lastIndexOfRemainder.get(targetRemainder)!;
32 // Update answer with the minimum length found so far.
33 answer = Math.min(answer, i - lastIndex);
34 }
35 // Update the map with the current prefix sum and its corresponding index.
36 lastIndexOfRemainder.set(currentPrefixSum, i);
37 }
38 // If answer is still equal to n, a valid subarray of length less than n was not found.
39 // Therefore, return -1. Otherwise, return answer.
40 return answer === n ? -1 : answer;
41}
42
Time and Space Complexity
Time Complexity
The time complexity of the given code is O(n)
, where n
is the length of the input list nums
. Here's why:
- There is a single loop that iterates over all the elements in
nums
. Inside the loop, the operations are a constant time: updatingcur
, calculatingtarget
, and checkingif target in last
. - The
in
operation for thelast
dictionary, which is checking if thetarget
is present in the keys oflast
, is anO(1)
operation on average because dictionary lookups in Python are assumed to be constant time under average conditions.
So, combining these together, we see that the time complexity is proportional to the length of nums
, hence O(n)
.
Space Complexity
The space complexity of the given code is also O(n)
, where n
is the length of the input list nums
. Here's why:
- A dictionary
last
is maintained to store indices of the prefix sums. In the worst case, if all the prefix sums are unique, the size of the dictionary could grow up ton
. - There are only a few other integer variables which don't depend on the size of the input, so their space usage is
O(1)
.
Therefore, because the predominant factor is the size of the last
dictionary, the space complexity is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.