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.
Example 4:
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.
Example 5:
Input: nums = [1000000000,1000000000,1000000000], p = 3 Output: 0
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= p <= 109
Solution: HashTable + Prefix Sum
Very similar to subarray target sum.
Basically, we are trying to find a shortest subarray that has sum % p equals to r = sum(arr) % p.
We use a hashtable to store the last index of the prefix sum % p and check whether (prefix_sum + p – r) % p exists or not.
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { public: int minSubarray(vector<int>& nums, int p) { const int n = nums.size(); int r = accumulate(begin(nums), end(nums), 0LL) % p; if (r == 0) return 0; unordered_map<int, int> m{{0, -1}}; // {prefix_sum % p -> last_index} int s = 0; int ans = n; for (int i = 0; i < n; ++i) { s = (s + nums[i]) % p; auto it = m.find((s + p - r) % p); if (it != m.end()) ans = min(ans, i - it->second); m[s] = i; } return ans == n ? -1 : ans; } }; |
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution: def minSubarray(self, nums: List[int], p: int) -> int: r = sum(nums) % p if r == 0: return 0 m = {0: -1} ans = len(nums) s = 0 for i, x in enumerate(nums): s = (s + x) % p t = (s + p - r) % p if t in m: ans = min(ans, i - m[t]) m[s] = i return -1 if ans == len(nums) else ans |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment