We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Make Sum Divisible by P

Number: 1694

Difficulty: Medium

Paid? No

Companies: Amazon, PhonePe, Meta, Samsung

Problem Description

Given an array of positive integers, the goal is to remove the smallest possible subarray (which can be empty) such that the sum of the remaining elements is divisible by a given integer p. Removing the entire array is not allowed. If it’s impossible to achieve a sum divisible by p, return -1.

Key Insights

  • Compute the total sum of the array and determine its remainder when divided by p.
  • If the total sum is already divisible by p (remainder equals 0), no elements need to be removed.
  • The problem can be reduced to finding a subarray whose sum has a remainder equal to the surplus (r) when the total sum is divided by p.
  • Use prefix sums and take modulo p at each step. Store seen remainders and their indices in a hash map.
  • For each prefix sum modulo value, checking for an earlier prefix sum with an appropriate modulo value facilitates identification of a subarray with the desired remainder.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array, since we iterate over the array once. Space Complexity: O(n), due to the hash map storing prefix modulo values and their indices.

Solution

The solution starts by calculating the remainder r when the total sum of the array is divided by p. If r is 0, the array’s sum is already divisible by p, so the answer is 0. Otherwise, we need to find the minimal contiguous subarray whose removal makes the remaining sum divisible by p.

To achieve this:

  1. Use a prefix sum and track its remainder modulo p.
  2. Maintain a hash map (or dictionary) to store the latest index for each prefix remainder.
  3. For each index, compute the current prefix sum modulo p. Then determine the target remainder by subtracting r (mod p) from the current prefix sum modulo p.
  4. If the target remainder exists in the hash map, update the minimum subarray length needed.
  5. Finally, if the minimum length equals the total array length (which means removing the whole array), return -1. Otherwise, return the minimum subarray length.

Code Solutions

# Python solution with comments:
class Solution:
    def minSubarray(self, nums, p):
        total = sum(nums)
        target = total % p
        # If the total sum is already divisible by p, no need to remove any subarray.
        if target == 0:
            return 0
        
        # Dictionary to store the latest index for each prefix sum modulo value.
        prefix_mod_dict = {0: -1}
        prefix = 0
        min_length = len(nums)
        
        # Iterate through the array while calculating the prefix modulo.
        for index, num in enumerate(nums):
            prefix = (prefix + num) % p
            # Compute the target modulo value needed from a previous prefix sum.
            needed_mod = (prefix - target) % p
            # If the needed modulo is present, a valid subarray is found.
            if needed_mod in prefix_mod_dict:
                min_length = min(min_length, index - prefix_mod_dict[needed_mod])
            # Record or update the current prefix modulo value with its index.
            prefix_mod_dict[prefix] = index
        
        # Verify that we did not end up removing the whole array.
        return -1 if min_length == len(nums) else min_length
        
# Example usage:
# sol = Solution()
# print(sol.minSubarray([3,1,4,2], 6))
← Back to All Questions