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.
Input Format
nums: an array of integersp: a positive integer
You may assume the array contains at least one element.
Output Format
Return a single integer: the minimum length of a contiguous subarray to remove, or -1 if no valid removal exists.
Constraints
- Elements may be positive, zero, or negative depending on the platform variant; use modulo normalization when computing remainders.
- If the total sum is already divisible by
p, the answer is0.
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.
Show 1 more example
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
Unlock deeper context for this problem
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.