Make Sum Divisible By P - Leetcode Solution

Problem Statement:

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: The sum of the elements in nums is 16, which is not divisible by 9. We can remove the subarrays [6,3] and [5,2]. Alternatively, we can remove the subarrays [3,5,2] and [6], or [5,6] and [3,2].

Solution:

The given problem can be solved by using the prefix sum and modulo operation.

The approach involves:

1. Finding the total sum of the given input array.

2. Calculating the modulo of the total sum with p, let's call it 'r'. If it is zero, then we don't need to remove any subarray, and the length is also 0.

3. If r is non-zero, then we need to find the minimum length subarray such that its sum's modulo with p is equal to r, If we find such a subarray, then we can remove the subarray and make the sum of the remaining elements divisible by p.

For step 3, we can use the prefix sum array and the modulo operation to find the subarray. We can iterate through the prefix sum array and for each prefix sum, we can calculate the modulo with p and store the index of the modulo's value in a hash map. If the prefix sum modulo p is r or larger than r, then we can subtract r from it and calculate the modulo again. If we find a modulo value in the hash map, then we can remove the subarray between the current index and the hash map's value index and return the length of this subarray.

Implementation:

Python:

def minSubarray(nums, p): r = sum(nums) % p if r == 0: return 0 remainders = {0: -1} curr_sum = 0 min_len = len(nums) for i in range(len(nums)): curr_sum = (curr_sum + nums[i]) % p remainder = (curr_sum - r) % p if remainder in remainders: min_len = min(min_len, i - remainders[remainder]) remainders[curr_sum] = i return -1 if min_len == len(nums) else min_len

Time Complexity: O(N), where N is the length of the input array.

Space Complexity: O(N), where N is the length of the input array.

Conclusion:

In this problem, we have learned how to find the minimum length subarray that can be removed from the input array such that the sum of the remaining elements is divisible by p. We have used the prefix sum, modulo, and hash map to solve the problem in O(N) time complexity and O(N) space complexity.

1