the third one in Biweekly Contest 35.
Difficulty : Medium
Related Topics : Array、Binary Search
Given an array of positive integers
nums
, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible byp
. 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.
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.
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.
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.
Input: nums = [1,2,3], p = 7 Output: -1 Explanation: There is no way to remove a subarray in order to get a sum divisible by 7.
Input: nums = [1000000000,1000000000,1000000000], p = 3 Output: 0
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= p <= 10^9
same as 974. Subarray Sums Divisible by K
- mine
- Java
Runtime: 35 ms, faster than 54.40%, Memory Usage: 61.1 MB, less than 45.12% of Java online submissions
// O(N)time // O(N)space public int minSubarray(int[] nums, int p) { int n = nums.length; int[] mod = new int[n + 1]; for(int i = 0; i < n; i++){ mod[i + 1] = ((mod[i] + nums[i]) % p + p) % p; } if(mod[n] == 0) return 0; HashMap<Integer, Integer> map = new HashMap<>(); map.put(0, 0); int res = n; for(int i = 1; i <= n; i++){ int temp = ((mod[i] - mod[n]) % p + p) % p; if(map.containsKey(temp)){ int l = i - map.get(temp); res = Math.min(l, res); } map.put(mod[i], i); } return res == n ? -1 : res; }
- Java
- the most votes
Runtime: 25 ms, faster than 99.85%, Memory Usage: 54.5 MB, less than 77.59% of Java online submissions
// O(N)time // O(N)space public int minSubarray(int[] nums, int p) { int l = nums.length; long sum = 0; for (int n : nums) sum += n; if (sum < p) return -1; if (sum % p == 0) return 0; Map<Integer, Integer> hm = new HashMap<>(); long curr = 0; int rem = (int) (sum % p); hm.put(0, -1); int ret = l; for (int i = 0; i < l; i++) { if (nums[i] % p == rem) return 1; curr += nums[i]; int cr = (int) (curr % p); int prev = cr >= rem ? cr - rem : cr - rem + p; if (hm.containsKey(prev)) ret = Math.min(ret, i - hm.get(prev)); hm.put(cr, i); } return ret == l ? -1 : ret; }