Remove the shortest contiguous subarray so the remaining array sum is divisible by .
Given an integer array nums and a positive integer p, remove one contiguous subarray (possibly empty only if the sum is already divisible) so that the sum of the remaining elements is divisible by p.
Return the minimum length of a subarray you need to remove. If it is impossible to make the sum divisible by p by removing a proper subarray, return -1.
The key idea is to work with prefix sums modulo p and find the shortest segment whose sum has the same remainder as the total array sum modulo p.
nums: an array of integersp: a positive integerYou may assume the array contains at least one element.
Return a single integer: the minimum length of a contiguous subarray to remove, or -1 if no valid removal exists.
p, the answer is 0.Example 1
Input
nums = [3,1,4,2], p = 6
Output
1
Explanation
The total sum is 10, and 10 % 6 = 4. Removing the subarray [4] leaves [3,1,2] with sum 6, which is divisible by 6.
Example 2
Input
nums = [6,3,5,2], p = 9
Output
2
Explanation
The total sum is 16, and 16 % 9 = 7. Removing [5,2] leaves [6,3] with sum 9, which is divisible by 9.
Example 3
Input
nums = [1,2,3], p = 3
Output
0
Explanation
The total sum is already divisible by 3, so no removal is needed.
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.