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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Make Sum Divisible by P

Difficulty: Medium

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.

Key Insights

  • The total sum of the array is calculated to check if it is already divisible by p.
  • If the total sum is divisible by p, the answer is 0 since no removal is needed.
  • If not, calculate the remainder of the total sum when divided by p.
  • Use a sliding window approach to find the smallest subarray that, when removed, makes the remaining sum divisible by p.
  • Maintain a hash map to store the most recent index of each prefix sum modulo p.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

  1. Calculate the total sum of the array.
  2. If the total sum is divisible by p, return 0.
  3. Calculate the remainder of the total sum when divided by p.
  4. Use a sliding window approach with two pointers to find the smallest subarray that can be removed.
  5. Store the prefix sums modulo p in a hash map to facilitate quick lookups.

Code Solutions

def minSubarray(nums, p):
    total_sum = sum(nums)
    remainder = total_sum % p
    
    if remainder == 0:
        return 0
    
    n = len(nums)
    min_length = float('inf')
    prefix_sum = 0
    prefix_index = {0: -1}  # Handle the case when prefix sum itself is the answer
    
    for i in range(n):
        prefix_sum += nums[i]
        prefix_mod = prefix_sum % p
        
        # Check if (prefix_mod - remainder) exists in the map
        target = (prefix_mod - remainder + p) % p
        
        if target in prefix_index:
            min_length = min(min_length, i - prefix_index[target])
        
        prefix_index[prefix_mod] = i  # Store the latest index of this prefix mod
    
    return min_length if min_length != float('inf') else -1
← Back to All Questions