#1590
Make Sum Divisible by P
specialist · 975 · lc medium +32 · premium · verified · 42.6% accepted · 2,858 likes · top 24%
Description
Given a positive integer array nums and integer p, remove the shortest contiguous subarray (possibly empty) from nums so the remaining elements have a sum divisible by p. Removing the whole array is not allowed. Return the length of the shortest such subarray, or -1 if no valid removal exists.
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.
Code
1
2
3