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
Answer
class Solution {
public int minSubarray(int[] nums, int p) {
long sum = 0;
for (int x : nums) {
sum += (long) x;
}
// It is not allowed to remove the whole array
if (sum < p)
return -1;
sum = sum % p;
if (sum == 0)
return 0;
// Now we want to find the smallest sub-array whose sum
// is equal to 'sum' or 'sum' + p' or 'sum' + 2*p...
Map<Integer, Integer> map = new HashMap<>();
int ans = nums.length;
long currSum = 0;
map.put(0, -1);
for (int i = 0; i < nums.length; i++) {
currSum += nums[i];
int mod = (int) (currSum % p);
map.put(mod, i);
// +p because of property of mod
int otherPart = (mod - (int) sum + p) % p;
if (map.containsKey(otherPart))
ans = Math.min(ans == -1 ? Integer.MAX_VALUE : ans, i - map.get(otherPart));
}
return ans < nums.length ? ans : -1;
}
}
Last updated