{x}
blog image

Make Sum Divisible by P

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 <= 105
  • 1 <= nums[i] <= 109
  • 1 <= p <= 109

Solution Explanation: Make Sum Divisible by P

This problem asks us to find the smallest subarray to remove from nums such that the sum of the remaining elements is divisible by p. We'll use a prefix sum approach combined with a hash table for efficient lookups.

Algorithm:

  1. Calculate the total sum modulo p: First, compute the sum of all elements in nums modulo p. Let's call this k. If k is 0, the sum is already divisible by p, so we return 0 (no subarray needs removal).

  2. Prefix Sum and Hash Table: We iterate through the array, calculating the prefix sum modulo p at each step. We store these prefix sums in a hash table (last), where the key is the prefix sum and the value is the index where that prefix sum last occurred.

  3. Finding the Target: For each prefix sum cur, we calculate the target prefix sum that, if found earlier, would indicate a subarray whose removal would make the remaining sum divisible by p. The formula for the target is (cur - k + p) % p. This accounts for the fact that we're working modulo p.

  4. Updating the Minimum Length: If we find a target in the last hash table, it means we've found a subarray to remove. The length of this subarray is i - last[target], where i is the current index. We update our minimum length (ans) accordingly.

  5. Handling Non-Existence: If after iterating, ans remains equal to the original length of nums, it means no suitable subarray was found, and we return -1.

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the nums array. We iterate through the array once. Hash table lookups are typically O(1) on average.

  • Space Complexity: O(n) in the worst case, as the hash table could store up to n entries (though it's often less).

Code Examples (Python):

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        k = sum(nums) % p
        if k == 0:
            return 0
        last = {0: -1}  # Initialize with index -1 for the initial sum 0
        cur = 0
        ans = len(nums)
        for i, x in enumerate(nums):
            cur = (cur + x) % p
            target = (cur - k + p) % p
            if target in last:
                ans = min(ans, i - last[target])
            last[cur] = i
        return -1 if ans == len(nums) else ans

The code in other languages (Java, C++, Go, Javascript, Typescript, Rust) follows a very similar structure, adapting the syntax and data structures as needed for each language. The core algorithm remains the same.