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 of p.
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 variable k holds the result of total sum modulo p which helps us identify what sum value needs to be removed (if possible) to make the overall sum divisible by p.
If k is 0, nothing needs to be removed since the total sum is already divisible by p. The solution will return 0 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 element x.
- Update the current prefix sum modulo p, store it in cur.
- Compute target, which is the prefix sum that we need to find in the last hash map. This is calculated as (cur - k + p) % p.
If the target is found in the last map, this means there exists a subarray whose sum modulo p is exactly k, and we could remove it to satisfy the condition. Update the ans with the minimum length found so far.
Update the hash map last with the current prefix sum modulo p 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 the ans 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 Evaluator

Example 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 with p gives us 14 % 5 = 4, which means k = 4. This indicates that we need to remove a subarray whose sum modulo p equals 4.
Since k is not 0, we understand that some elements need to be removed. If k were 0, it would imply no removal is necessary, and we could return 0.
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 element 3, cur = 3 % 5 = 3. We calculate target = (3 - 4 + 5) % 5 = 4. Since target is not found in last, we proceed without any removal.
- Updating last to {0: -1, 3: 0}.
- At index 1 with element 1, cur = (3 + 1) % 5 = 4. We calculate target = (4 - 4 + 5) % 5 = 0. The target is found in last, indicating a potential subarray from index -1 to 1. 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 element 4, cur = (4 + 4) % 5 = 3. We calculate target = (3 - 4 + 5) % 5 = 4, and last already has a 4. 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 element 6, cur = (3 + 6) % 5 = 4. We calculate target = (4 - 4 + 5) % 5 = 0 again. The target is in last, suggesting a potential subarray from index -1 to 3. However, this insight needs correction.
Upon closer examination, we realize the mistake in our previous assessment. The correct approach is to identify the subarray [4] at index 2, which has a length of 1 and a sum of 4, which is exactly k. Removing this subarray leaves us with a sum of 10, which is divisible by p=5.
Therefore, the corrected answer for the input nums = [3, 1, 4, 6] and p = 5 is 1. This indicates that the shortest subarray we can remove to make the sum of the remaining elements divisible by 5 has a length of 1.

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: updating cur, calculating target, and checking if target in last.
The in operation for the last dictionary, which is checking if the target is present in the keys of last, is an O(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 to n.
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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know