Make Sum Divisible by P
Medium
2 views
Topics:
ArraysSliding Windows
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
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What are the upper and lower bounds for the values in the `nums` array and the value of `p`?
- Can `p` ever be equal to 0 or 1?
- If there are multiple subarrays of the same minimum length that satisfy the condition, is any one of them acceptable?
- If the sum of all elements in `nums` is already divisible by `p`, should I return 0, or should I still look for a subarray to remove?
- Can the input array `nums` be empty or null?
Brute Force Solution
Approach
The brute force method for this problem involves checking every possible part of the list of numbers. We want to find the smallest part we can remove so that the sum of the remaining numbers is evenly divisible by a given number.
Here's how the algorithm would work step-by-step:
- First, calculate the sum of all the numbers in the list.
- Then, try removing a single number from the list and check if the sum of the remaining numbers is divisible by the given number. If it is, we've found a solution.
- If removing a single number didn't work, try removing pairs of numbers. Check every possible pair to see if the sum of the remaining numbers is divisible by the given number.
- Continue this process by trying to remove groups of three numbers, then four, and so on, each time checking all possible combinations.
- Keep track of the smallest group of numbers we can remove to make the sum of the remaining numbers divisible by the given number.
- If we find a solution, we're done. If we have tried removing all possible combinations of numbers and haven't found a solution, it means we must remove the entire list of numbers to make the sum divisible by the given number (since zero is divisible by any number).
Code Implementation
def make_sum_divisible_by_p_brute_force(numbers, divisor):
list_length = len(numbers)
total_sum = sum(numbers)
for removal_count in range(list_length + 1):
for indices_to_remove in combinations(range(list_length), removal_count):
current_sum = total_sum
# Subtract the numbers at the indices being removed
for index in indices_to_remove:
current_sum -= numbers[index]
# Check if the remaining numbers are divisible by the divisor
if current_sum % divisor == 0:
return removal_count
return list_length
from itertools import combinations
Big(O) Analysis
Time Complexity
O(n^3) – The brute force method iterates through all possible sub-sequences to remove. The outer loop iterates from 1 to n (the size of the input array nums) representing the size of sub-sequence to remove. Then, there's another loop to select all combinations of that size. For each combination, we calculate the sum of the remaining numbers and check divisibility by p which is O(n). The combination generation scales as O(n choose k) which is upper-bounded by O(n^2). Therefore the complexity is O(n * n^2) which simplifies to O(n^3).
Space Complexity
O(1) – The brute force solution, as described, primarily involves iterative calculations without significant auxiliary data structures. While it considers combinations of elements to remove, it doesn't explicitly store all combinations simultaneously. It only needs to store a variable to track the size of the smallest group of numbers to remove. Therefore, the auxiliary space used remains constant regardless of the input size N, making the space complexity O(1).
Optimal Solution
Approach
The key idea is to find a smallest segment we can remove from the list, such that the remaining list sums to a multiple of the given number. To do this efficiently, we look for a segment whose sum is equal to the original sum's remainder after division.
Here's how the algorithm would work step-by-step:
- First, calculate the sum of all the numbers and then find the remainder after dividing it by the given number.
- If the remainder is zero, then we don't need to remove any numbers, and the answer is zero.
- Otherwise, we need to find the shortest group of numbers whose sum has the same remainder.
- To do this, keep track of the running sum's remainder as we go through the list.
- Whenever we encounter a remainder that we've seen before, it means that the group of numbers in between has a sum that is a multiple of the given number.
- But what we're really looking for is a group of numbers that, when removed, leave behind a total sum that's a multiple of the target number. So, we're looking for a group whose sum has the same remainder as the original remainder.
- Keep track of where you have seen each remainder, and the shortest group that produces the original remainder.
- After looking through the entire list, return the length of the shortest group that has the required remainder.
- If you can't find any such group, it means you can't make the list's sum a multiple of the given number by removing some of the numbers, so remove the entire list.
Code Implementation
def make_sum_divisible_by_p(numbers, divisor):
list_length = len(numbers)
total_sum = sum(numbers)
remainder = total_sum % divisor
# If the remainder is 0, no removal needed.
if remainder == 0:
return 0
prefix_remainder_index = {0: -1}
min_removal_length = list_length
current_sum = 0
for index, number in enumerate(numbers):
current_sum = (current_sum + number) % divisor
# We look for a sub-array with sum equal to the original remainder.
required_remainder = (current_sum - remainder) % divisor
if required_remainder in prefix_remainder_index:
current_removal_length = index - prefix_remainder_index[required_remainder]
min_removal_length = min(min_removal_length, current_removal_length)
# Store the earliest index of the current remainder.
if current_sum not in prefix_remainder_index:
prefix_remainder_index[current_sum] = index
# If no valid sub-array is found, remove the entire list.
if min_removal_length == list_length:
return -1
return min_removal_lengthBig(O) Analysis
Time Complexity
O(n) – The algorithm iterates through the input array of size n once to calculate the initial sum and its remainder. It then iterates through the array again, maintaining a running sum and using a hash map (or dictionary) to store remainders and their indices. Hash map operations (put and get) take O(1) time on average. The algorithm finds the shortest subarray whose sum has the same remainder as the initial remainder. Therefore, the dominant operation is iterating through the array, resulting in O(n) time complexity.
Space Complexity
O(min(N, P)) – The primary auxiliary space usage comes from the hash map used to store the running sum's remainders and their corresponding indices. In the worst case, we might store all remainders encountered, up to N of them. However, since we are taking the remainder with respect to P, the maximum number of distinct remainders possible is P. Therefore, the space used by the hash map is bounded by the minimum of N and P. Thus, the space complexity is O(min(N, P)).
Edge Cases
| Case | How to Handle |
|---|---|
| Empty input array | Return 0 if the sum is already divisible by p; otherwise return -1 since no subarray can be removed from an empty array to affect divisibility. |
| Input array of length 1 | If the element is not divisible by p, return 1; otherwise, return 0 if the initial sum was divisible, or -1 if it isn't and we cannot remove. |
| Initial sum is already divisible by p | Return 0 because no subarray needs to be removed. |
| No subarray exists that satisfies the condition | Return -1 when no valid subarray can be found, indicating the task is impossible. |
| Large input array causing potential integer overflow when calculating the sum | Use modulo operator (%) after each addition to prevent integer overflow. |
| p equals 1 | Return 0 since any number is divisible by 1. |
| All elements in the array are divisible by p | If the initial sum is divisible by p, return 0; otherwise, return 1 if removing a single element makes the remaining sum divisible by p, and -1 otherwise. |
| The required remainder does not appear in the prefix sums | Return -1, indicating no such subarray can be removed to make the sum divisible by p. |
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
