Make Sum Divisible by P
Problem Description
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.
Examples:
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.
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.
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 <= 10⁵
1 <= nums[i] <= 10⁹
1 <= p <= 10⁹
Brute Force Approach
Ok, one basic approach that comes to mind is to do exactly what is asked in the problem statement.
Just take the sum of all the subarrays and subtract it from the total sum of the array. If the result is divisible by k, then store it as the answer.
Do this for all the subarrays and return the minimum possible answer.
If it’s not possible, then simply return -1.
How to do it?
The basic approach to solve this problem is to follow the problem statement directly:
- Compute the total sum of the array, totalSum.
- Iterate over all possible subarrays in the array:
- For each subarray, calculate its sum, subarraySum.
- Compute the remaining sum after removing the subarray:
remainingSum = totalSum - subarraySum. - Check if remainingSum is divisible by p.
- If divisible, store the length of the subarray as a potential answer.
- Return the minimum length among all such valid subarrays.
- If no valid subarray is found, return -1.
Let's understand it with and example:
Let's dry run the approach on nums = [3, 5, 2] and p = 3:
- Total Sum:
totalSum = 3 + 5 + 2 = 10 - Iterate through all possible subarrays:
- Subarray: [3]
subarraySum = 3, remainingSum = 10 - 3 = 7.
7 % 3 ≠ 0. - Subarray: [5]
subarraySum = 5, remainingSum = 10 - 5 = 5.
5 % 3 ≠ 0. - Subarray: [2]
subarraySum = 2, remainingSum = 10 - 2 = 8.
8 % 3 ≠ 0. - Subarray: [3, 5]
subarraySum = 8, remainingSum = 10 - 8 = 2.
2 % 3 ≠ 0. - Subarray: [5, 2]
subarraySum = 7, remainingSum = 10 - 7 = 3.
3 % 3 = 0 ✅ (Valid).
Length of subarray = 2.
- Subarray: [3]
- Result:
The smallest valid subarray is [5, 2], and its length is 2. Return 2.
How to code it up:
Here are the concise steps to implement the solution:
- Calculate the total sum of the array using accumulate.
- Check if the total sum is divisible by p. If yes, return 0 (no subarray needs to be removed).
- Initialize variables:
- Set len to the array size (n).
- Iterate over all possible subarrays:
- Use two loops to go through all subarrays.
- For each subarray, calculate its sum (subSum).
- Check divisibility of the remaining sum (totalSum - subSum) by p. If divisible, update len with the smaller subarray length.
- Return the result: If no valid subarray is found, return -1. Otherwise, return the smallest length len.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
int minSubarray(vector<int>& nums, int p) {
// Step 1: Calculate the total sum of the array
long long sum = accumulate(nums.begin(), nums.end(), 0LL);
// Step 2: If the total sum is already divisible by p, return 0 (no subarray needs to be removed)
if(sum % p == 0)
return 0;
// Length of the array
int n = nums.size();
// Initialize len to the maximum possible subarray length (whole array)
int len = n;
// Step 3: Iterate over all possible subarrays
for(int i = 0; i < n; i++) {
// To hold the sum of elements for the current subarray
long long subSum = 0;
// Step 4: Iterate through all subarrays starting from index i
for(int j = i; j < n; j++) {
// Add the current element to the subarray sum
subSum += nums[j];
// Step 5: Check if the remaining sum (totalSum - subSum) is divisible by p
// and if the length of the subarray is smaller than the current smallest length
if((sum - subSum) % p == 0 && (j - i + 1) < len)
// Update the minimum length if the condition is satisfied
len = j - i + 1;
}
}
// Step 6: If no valid subarray was found, return -1
// Otherwise, return the smallest subarray length found
return len == n ? -1 : len;
}
};
2. Java Try on Compiler
class Solution {
public int minSubarray(int[] nums, int p) {
// Step 1: Calculate the total sum of the array
long sum = 0;
for (int num : nums) {
sum += num;
}
// Step 2: If the total sum is already divisible by p, return 0 (no subarray needs to be removed)
if (sum % p == 0) {
return 0;
}
// Length of the array
int n = nums.length;
// Initialize len to the maximum possible subarray length (whole array)
int len = n;
// Step 3: Iterate over all possible subarrays
for (int i = 0; i < n; i++) {
long subSum = 0;
// Step 4: Iterate through all subarrays starting from index i
for (int j = i; j < n; j++) {
subSum += nums[j];
// Step 5: Check if the remaining sum (totalSum - subSum) is divisible by p
// and if the length of the subarray is smaller than the current smallest length
if ((sum - subSum) % p == 0 && (j - i + 1) < len) {
len = j - i + 1;
}
}
}
// Step 6: If no valid subarray was found, return -1
// Otherwise, return the smallest subarray length found
return len == n ? -1 : len;
}
}
3. Python Try on Compiler
class Solution:
def minSubarray(self, nums, p):
# Step 1: Calculate the total sum of the array
total_sum = sum(nums)
# Step 2: If the total sum is already divisible by p, return 0 (no subarray needs to be removed)
if total_sum % p == 0:
return 0
# Length of the array
n = len(nums)
# Initialize len to the maximum possible subarray length (whole array)
min_len = n
# Step 3: Iterate over all possible subarrays
for i in range(n):
sub_sum = 0
# Step 4: Iterate through all subarrays starting from index i
for j in range(i, n):
sub_sum += nums[j]
# Step 5: Check if the remaining sum (totalSum - subSum) is divisible by p
# and if the length of the subarray is smaller than the current smallest length
if (total_sum - sub_sum) % p == 0 and (j - i + 1) < min_len:
min_len = j - i + 1
# Step 6: If no valid subarray was found, return -1
# Otherwise, return the smallest subarray length found
return -1 if min_len == n else min_len
4. Javascript Try on Compiler
/**
* @param {number[]} nums
* @param {number} p
* @return {number}
*/
var minSubarray = function(nums, p) {
// Step 1: Calculate the total sum of the array
let sum = nums.reduce((acc, num) => acc + num, 0);
// Step 2: If the total sum is already divisible by p, return 0 (no subarray needs to be removed)
if (sum % p === 0) {
return 0;
}
// Length of the array
let n = nums.length;
// Initialize len to the maximum possible subarray length (whole array)
let len = n;
// Step 3: Iterate over all possible subarrays
for (let i = 0; i < n; i++) {
let subSum = 0;
// Step 4: Iterate through all subarrays starting from index i
for (let j = i; j < n; j++) {
subSum += nums[j];
// Step 5: Check if the remaining sum (totalSum - subSum) is divisible by p
// and if the length of the subarray is smaller than the current smallest length
if ((sum - subSum) % p === 0 && (j - i + 1) < len) {
len = j - i + 1;
}
}
}
// Step 6: If no valid subarray was found, return -1
// Otherwise, return the smallest subarray length found
return len === n ? -1 : len;
};
Time Complexity: O(n²)
The outer loop iterates from i = 0 to n - 1. This means the outer loop executes n times.
For each iteration of the outer loop (with a fixed starting point i), the inner loop iterates from i to n - 1.
The total number of iterations across all outer and inner loops is therefore the sum:
n + (n - 1) + (n - 2) + ... + 1.
The above sum can be computed using the formula for the sum of the first n natural numbers:
S = (n * (n + 1)) / 2.
Substituting into the formula, the total number of iterations is proportional to n², which dominates the time complexity.
Hence, the time complexity of the brute force solution is O(n²).
Space Complexity: O(n)
Auxiliary Space Complexity: O(1)
The solution uses only a few variables (sum, subSum, len, and n are used), which require O(1) space.
Total Space Complexity: O(n)
The input array nums is given, which requires O(n) space.
Adding this to the auxiliary space gives: Total Space Complexity = O(n)
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(n²), which is not suitable for n ≤ 10⁵. This means that for each test case, where the size of the array is at most 10⁵, the solution might not execute within the given time limits.
Since O(n²) results in a maximum of 10¹⁰ operations (for n = 10⁵), the solution is not expected to work well for larger test cases. In most competitive programming environments, problems can handle up to 10⁶ operations per test case, meaning that for n ≤ 10⁵, the solution with 10¹⁰ operations is not efficient enough.
When multiple test cases are involved, the total number of operations could easily exceed this limit and approach 10¹⁰ operations, especially when there are many test cases or the value of n increases.
Thus, while the solution meets the time limits for a single test case, the O(n²) time complexity poses a risk for Time Limit Exceeded (TLE) errors when handling larger input sizes or multiple test cases. This can be a challenge for competitive programming problems with larger inputs or numerous test cases.
Can we optimize it?
Yes, of course!
We can definitely optimize it—let's do it!
In the previous approach, we checked all possible subarrays, calculated their sums, and then checked if the difference of total sum and subarray sum is divisible by p, and if yes we returned length of minimum such subarray. While it worked, it wasn't feasible because it gave us an O(n²) solution.
But don't worry—here’s how we can make it efficient!
Now, let’s analyze the drawback in our previous approach.
The issue was that we calculated the sum of every possible subarray. That’s where we lost efficiency—doing redundant work over and over.
Let’s fix this by eliminating the need to recompute sums repeatedly.
Yes, exactly! Let’s break it down step by step.
What do we do to get the sum of a subarray from index 0 to i?
We just calculate the sum of all elements from the start to index i, right?
But what if there’s an index j somewhere between 0 and i, and now you need the sum of the subarray from j to i?
Simple! You calculate the sum from 0 to i and subtract the sum from 0 to j-1. Easy, right?
Now, to make it efficient, we can precompute and store the sum up to each index, we call it Prefix Sum. This allows us to quickly get the sum of any subarray by subtracting one precomputed value from another.
Great! Now we need to know the minimum length of a subarray whose sum we can reduce from the total sum of the array so that the remaining sum becomes divisible by p.
Okay, we need to remove the subarray sum from the total sum, but what can we minimally reduce from the total sum to make it divisible by p?
Yes! we can divide total_sum by p and whatever the remainder comes we can subtract it from total_sum, to make our total sum perfectly divisible by p, or we can say we can reduce total_sum%p from total sum.
Hence, let's say our target is total_sum % p.
Now, Let's analyze this mathematically:
We are given an array nums and need to find the smallest subarray sum in nums such that, if we reduce it from the total sum of nums, the result becomes divisible by p.
In other words,
(sum(nums) - sum(nums[j:i])) % p = 0,
where sum(nums[j:i]) is the sum of a subarray from index j to i.
Using the prefix sum concept, we can express this sum(nums[j:i]) as:
Prefix[i] - Prefix[j-1], substituting it into the equation:
(sum(nums) - (Prefix[i] - Prefix[j-1])) % p = 0.
Rearranging the equation:
sum(nums) - (Prefix[i] - Prefix[j-1]) = k * p, where k is any integer.
Taking modulo p on both sides:
(Prefix[i] - Prefix[j-1]) % p = (sum(nums) - k * p) % p.
Using the distributive property of modulo:
(Prefix[i] - Prefix[j-1]) % p = (sum(nums) % p - 0) (as k * p % p = 0, since p % p = 0).
Thus:
(Prefix[i] - Prefix[j-1]) % p = sum(nums) % p,
or equivalently,
Prefix[j-1] % p = Prefix[i] % p - sum(nums) % p.
Adding modulo operation:
Prefix[j-1] % p = (Prefix[i] % p - sum(nums) % p) % p,
where Prefix[i] represents the current_subarray_sum (from index 0 to i) and sum(nums) % p is the target (as discussed earlier).
Prefix[j-1] represents the subarray sum till index j-1, where j-1 < i.
To ensure consistency, we add p in (current_subarray_sum - target + p) % p. This is necessary because (current_subarray_sum - target) can sometimes be negative, which would result in negative values during the modulo operation. Such negative values could disrupt the consistency of hash values.
By adding p before applying the modulo operation, we ensure the result remains within a positive range. This keeps the values consistent and allows us to efficiently track and identify the required subarray sums.
Hence, we will iterate through the array nums, keeping track of the current_subarray_sum by adding each element to the previous sum and taking mod p. We will store these modulo values in a hashmap to track their indices.
If at any point we find that (current_subarray_sum - target + p) % p exists in the hashmap, it means this value has been encountered before. The subarray between the previously stored index and the current index has a sum that, when reduced, makes the total sum divisible by p.
This subarray's length can then be stored as a potential answer. By continuously checking, we ensure we keep track of the smallest subarray length.
Finally, after completing the iteration, we return the minimum length subarray found. If no valid subarray is found, we return -1.
By leveraging this property, we can identify the subarray whose removal will make the remaining sum divisible by p in a computationally efficient way.
This approach avoids the need for explicitly calculating every subarray sum multiple times, making it more efficient.
Steps to do it:
- First, compute the total sum of the array: total_sum = sum(nums).
- Calculate the remainder of total_sum when divided by p: remainder = total_sum % p.
- If remainder == 0, return 0 immediately because no subarray needs to be removed (the total sum is already divisible by p).
- The target value that we want to find a subarray sum for is: target = remainder.
- Initialize an empty map (hashmap) to store the prefix sums modulo p and their corresponding indices.
- Initialize a variable min_len = n (where n is the length of the array) to keep track of the smallest length of the subarray that matches the target.
- As you iterate through the array, keep track of the cumulative sum (current_sum) of elements so far.
- For each element nums[i]:
- Update the current_sum = (current_sum + nums[i]) % p.
- For each element nums[i]:
- If (current_sum - target + p) % p == 0, it means the subarray starting from the index after the first occurrence of this sum to the current index has a sum equal to the target.
- If the target subarray sum is found, calculate its length: len = i - map[current_sum - target].
- If the length of this subarray is smaller than min_len, update min_len.
- Store the current cumulative sum modulo p in the hashmap: map[current_sum] = i.
- If min_len has been updated from its initial value, return min_len.
- If no valid subarray was found, return -1.
Let's understand with an example:
Let's walk through a concise dry run of the algorithm using nums = [6, 3, 5, 2] and p = 9.
- Calculate the total sum:
- total_sum = 6 + 3 + 5 + 2 = 16
- Compute the target:
- remainder = total_sum % p = 16 % 9 = 7
- target = 7
- Initialize variables:
- min_len = n = 4 (length of the array)
- map = {} (hashmap to store prefix sums modulo p)
- Iterate through the array
current_sum = 0
We will iterate through each element, updating current_sum and checking for subarrays.
1. Iteration 1 (i = 0, nums[0] = 6):
- current_sum = (0 + 6) % 9 = 6
- map = {6: 0} (Store the prefix sum modulo p at index 0)
- Iteration 2 (i = 1, nums[1] = 3):
- current_sum = (6 + 3) % 9 = 0
- map = {6: 0, 0: 1} (Store the prefix sum modulo p at index 1)
- Iteration 3 (i = 2, nums[2] = 5):
- current_sum = (0 + 5) % 9 = 5
- map = {6: 0, 0: 1, 5: 2} (Store the prefix sum modulo p at index 2)
- Iteration 4 (i = 3, nums[3] = 2):
- current_sum = (5 + 2) % 9 = 7
- current_sum - target = 7 - 7 = 0
- Found target: Since map[0] = 1, the subarray from index 1 to index 3 has sum equal to 7.
- Subarray length = 3 - 1 = 2
- min_len = 2 (Update the minimum length to 2)
- Return the result:
- min_len = 2, so the minimum length of the subarray to remove is 2.
How to code it up:
- Calculate Total Sum:
- Use accumulate() to calculate the total sum of the array.
- Compute the remainder of the total sum modulo p. If it is 0, return 0 immediately.
- Initialize Variables:
- Use a hashmap (unordered_map) to store prefix sums modulo p and their indices. Initialize it with {0: -1} to handle edge cases.
- Initialize variables for the current cumulative sum (current_sum = 0) and the minimum subarray length (min_length = n).
- Iterate Through the Array:
- For each element in the array:
- Add the current element to the cumulative sum.
- Compute the current remainder modulo p.
- Compute the target remainder that would make the remaining sum divisible by p using:
target = (current_remainder - remainder + p) % p. - Check if this target remainder exists in the hashmap:
- If found, calculate the subarray length and update min_length if it's smaller.
- Update the hashmap with the current remainder and its index.
- Return the Result:
- If no valid subarray is found (i.e., min_length == n), return -1. Otherwise, return min_length.
Code Implementation
1. C++ Try on Compiler
using ll = long long;
class Solution {
public:
int minSubarray(vector<int>& nums, int p) {
// Step 1: Calculate the total sum of the array
ll total_sum = accumulate(nums.begin(), nums.end(), 0ll);
int n = nums.size();
// Step 2: Compute the remainder of total_sum % p
int remainder = total_sum % p;
// If total_sum is already divisible by p, no subarray needs to be removed
if (remainder == 0) return 0;
// Step 3: Initialize variables
unordered_map<int, int> prefix_sum_map;
// To handle the case where the subarray starts from index 0
prefix_sum_map[0] = -1;
// Cumulative sum of elements while iterating through the array
ll current_sum = 0;
// The minimum length of subarray to remove
int min_length = n;
// Step 4: Iterate through the array to find subarrays whose sum matches the target
for (int i = 0; i < n; i++) {
// Update the cumulative sum
current_sum += nums[i];
// Compute current_sum % p
int current_remainder = current_sum % p;
// Compute the target sum needed to make the remaining sum divisible by p
int target = (current_remainder - remainder + p) % p;
// Step 5: Check if we have previously encountered the target sum
if (prefix_sum_map.find(target) != prefix_sum_map.end()) {
// Calculate the length of the subarray that can be removed
min_length = min(min_length, i - prefix_sum_map[target]);
}
// Step 6: Update the map with the current remainder
prefix_sum_map[current_remainder] = i;
}
// Step 7: Return the result
// If no valid subarray is found, return -1
return min_length == n ? -1 : min_length;
}
};
2. Java Try on Compiler
import java.util.*;
class Solution {
public int minSubarray(int[] nums, int p) {
// Step 1: Calculate the total sum of the array
long totalSum = 0;
for (int num : nums) {
totalSum += num;
}
int n = nums.length;
// Step 2: Compute the remainder of totalSum % p
int remainder = (int)(totalSum % p);
// If totalSum is already divisible by p, no subarray needs to be removed
if (remainder == 0) return 0;
// Step 3: Initialize variables
Map<Integer, Integer> prefixSumMap = new HashMap<>();
prefixSumMap.put(0, -1); // To handle the case where the subarray starts from index 0
long currentSum = 0; // Cumulative sum of elements while iterating through the array
int minLength = n; // The minimum length of subarray to remove
// Step 4: Iterate through the array to find subarrays whose sum matches the target
for (int i = 0; i < n; i++) {
// Update the cumulative sum
currentSum += nums[i];
// Compute currentSum % p
int currentRemainder = (int)(currentSum % p);
// Compute the target sum needed to make the remaining sum divisible by p
int target = (currentRemainder - remainder + p) % p;
// Step 5: Check if we have previously encountered the target sum
if (prefixSumMap.containsKey(target)) {
// Calculate the length of the subarray that can be removed
minLength = Math.min(minLength, i - prefixSumMap.get(target));
}
// Step 6: Update the map with the current remainder
prefixSumMap.put(currentRemainder, i);
}
// Step 7: Return the result
// If no valid subarray is found, return -1
return minLength == n ? -1 : minLength;
}
}
3. Python Try on Compiler
class Solution:
def minSubarray(self, nums, p):
# Step 1: Calculate the total sum of the array
total_sum = sum(nums)
n = len(nums)
# Step 2: Compute the remainder of total_sum % p
remainder = total_sum % p
# If total_sum is already divisible by p, no subarray needs to be removed
if remainder == 0:
return 0
# Step 3: Initialize variables
prefix_sum_map = {0: -1} # To handle the case where the subarray starts from index 0
current_sum = 0 # Cumulative sum of elements while iterating through the array
min_length = n # The minimum length of subarray to remove
# Step 4: Iterate through the array to find subarrays whose sum matches the target
for i in range(n):
# Update the cumulative sum
current_sum += nums[i]
# Compute current_sum % p
current_remainder = current_sum % p
# Compute the target sum needed to make the remaining sum divisible by p
target = (current_remainder - remainder + p) % p
# Step 5: Check if we have previously encountered the target sum
if target in prefix_sum_map:
# Calculate the length of the subarray that can be removed
min_length = min(min_length, i - prefix_sum_map[target])
# Step 6: Update the map with the current remainder
prefix_sum_map[current_remainder] = i
# Step 7: Return the result
# If no valid subarray is found, return -1
return -1 if min_length == n else min_length
4. Javascript Try on Compiler
/**
* @param {number[]} nums
* @param {number} p
* @return {number}
*/
var minSubarray = function(nums, p) {
// Step 1: Calculate the total sum of the array
let totalSum = nums.reduce((acc, num) => acc + num, 0);
let n = nums.length;
// Step 2: Compute the remainder of totalSum % p
let remainder = totalSum % p;
// If totalSum is already divisible by p, no subarray needs to be removed
if (remainder === 0) return 0;
// Step 3: Initialize variables
let prefixSumMap = new Map();
prefixSumMap.set(0, -1); // To handle the case where the subarray starts from index 0
let currentSum = 0; // Cumulative sum of elements while iterating through the array
let minLength = n; // The minimum length of subarray to remove
// Step 4: Iterate through the array to find subarrays whose sum matches the target
for (let i = 0; i < n; i++) {
// Update the cumulative sum
currentSum += nums[i];
// Compute currentSum % p
let currentRemainder = currentSum % p;
// Compute the target sum needed to make the remaining sum divisible by p
let target = (currentRemainder - remainder + p) % p;
// Step 5: Check if we have previously encountered the target sum
if (prefixSumMap.has(target)) {
// Calculate the length of the subarray that can be removed
minLength = Math.min(minLength, i - prefixSumMap.get(target));
}
// Step 6: Update the map with the current remainder
prefixSumMap.set(currentRemainder, i);
}
// Step 7: Return the result
// If no valid subarray is found, return -1
return minLength === n ? -1 : minLength;
};
Time Complexity: O(n)
First, the array was iterated through once to calculate the total sum using accumulate() or a similar function. This step took O(n) time.
Next, a single pass was made through the array to find the subarray that satisfied the condition. For each element, the cumulative sum, remainder, and target value were calculated.
Lookups and updates were performed in a hashmap, which on average took O(1) per operation. This also took O(n) time.
Thus, the overall time complexity of the solution was O(n).
This approach was efficient because it involved just a single pass through the array and used a hashmap for constant-time lookups.
Space Complexity: O(n)
- Auxiliary Space Complexity: O(n)
The primary additional space usage is for the hashmap (prefix_sum_map), which stores at most n key-value pairs, where n is the size of the array.
Each key-value pair takes O(1) space, so the auxiliary space for the hashmap is O(n). - Total Space Complexity: O(n)
In addition to the input array, which is given as part of the problem and takes O(n) space, the total space usage includes the auxiliary space from the hashmap.
Thus, the total space complexity is O(n + n) = O(n).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given an array of integer nums and an integer k, return the total number of continuous subarrays whose sum equals k.
Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.
A subarray is a contiguous part of an array.