Leetcode Daily Question 03/10/2024 - 1590. 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.

from typing import List
class Solution:
  def minSubarray(self, nums: List[int], p: int) -> int:
    remainder = sum(nums) % p
    if remainder == 0:
      return 0
    
    min_length = float('inf')
    curr_sum = 0
    prefix_sum_mod = {0: -1}
    
    for i in range(len(nums)):
      curr_sum += nums[i]
      mod_val = curr_sum % p
      
      target = (mod_val - remainder) % p
      if target in prefix_sum_mod:
        min_length = min(min_length, i - prefix_sum_mod[target])
      
      prefix_sum_mod[mod_val] = i
      
    
    return min_length if min_length < len(nums) else -1

Explanation:

The idea is to find a subarray such that the difference between two prefix sums is divisible by
𝑝
p. This ensures that removing this subarray makes the sum of the remaining elements divisible by
𝑝
p.

We use a prefix_sum_mod map to track the current prefix sum modded by p, along with the rightmost index where this modded value appears.

The index is important because it tells us the length of the subarray that would be removed.

Given the total sum's remainder when divided by p, we subtract the current prefix sum modded by p to find the target remainder. If we have seen this target before in the map, it means we have found a subarray removal that makes the remaining sum divisible by p.

Let us demonstrate this with an example.

nums = [3,1,4,2]
p = 6

prefix_sum_mod = {0: -1} # Incase we need to remove the first element.

total = 10 
total % p = 4
remainder = 4

nums[0:1] % p = 3
3 - remainder = -1 % 6 = 5, This does not make the rest divisible by p, so we do not remove.
prefix_sum_mod = {0: -1, 3: 0}

nums[0:2] % p = 4
4 - reaminder= 0
Equivalenting to removing [1:3], giving [4,2] which is divisible by 6
min_length = min(min_length, i - prefix_sum_mod[0]) = 2
prefix_sum_mod = {0: -1, 3: 0, 4: 1}

nums[0:3] % p = 2
2 - remainder = -2 % 6 = 4
Equivalenting to removing [4], giving [1,3,2] which is divislbe by 6
min_length = 1
perfix_sum_mod = {0: -1, 3: 0, 4: 1, 2: 2}

nums[0:4] % p = 4
4 - remainder = 0
Equivalenting to removing the whole array, which is not allowed.
perfix_sum_mod = {0: -1, 3: 0, 4: 3, 2: 2}

Putting this into code.

def minSubarray(nums, p):
  remainder = sum(nums) % p
  
  if remainder == 0:  # There is nothing to remove
    return 0
  
  min_length = float('inf')
  curr_sum = 0
  prefix_sum_mod = {0: -1}  # Incase we need to remove the first element
  
  for i in range(len(nums)):
    curr_sum += i
    mod_val = curr_sum % p
    
    target = (mod_val - remainder) % p
    if target in prefix_sum_mod:
      min_length = min(min_length, i - prefix_sum_mod[target])
      
    prefix_sum_mod[mod_val] = i
    
    
  return -1 if min_length < len(nums) else min_length

The time complexity is O(n) as we iterate through the array to calculate sum() and perform prefix search.

The space complexity is O(n) as we store the prefix sum for lookup.

The full solution can be found near the top of the page.