You are given two arrays nums1
and nums2
consisting of positive integers.
You have to replace all the 0
‘s in both arrays with strictly positive integers such that the sum of elements of both arrays becomes equal.
Return the minimum equal sum you can obtain, or -1
if it is impossible.
Example 1:
Input: nums1 = [3,2,0,1,0], nums2 = [6,5,0] Output: 12 Explanation: We can replace 0's in the following way: - Replace the two 0's in nums1 with the values 2 and 4. The resulting array is nums1 = [3,2,2,1,4]. - Replace the 0 in nums2 with the value 1. The resulting array is nums2 = [6,5,1]. Both arrays have an equal sum of 12. It can be shown that it is the minimum sum we can obtain.
Example 2:
Input: nums1 = [2,0,2,0], nums2 = [1,4] Output: -1 Explanation: It is impossible to make the sum of both arrays equal.
Constraints:
1 <= nums1.length, nums2.length <= 105
0 <= nums1[i], nums2[i] <= 106
Solution: A few cases
Calculate the sum of number of zeros of each array as (s1, z1), (s2, z2). There are a few cases:
- z1 == z2 == 0, there is no way to change, just check s1 == s2.
- z1 == 0, z1 != 0 or z2 == 0, z1 != 0. Need to at least increase the sum by number of zeros, check s1 + z1 <= s2 / s2 + z2 <= s1
- z1 != 0, z2 != 0, the min sum is max(s1 + z1, s2 + z2)
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua class Solution { public: long long minSum(vector<int>& nums1, vector<int>& nums2) { auto getSumAndZeros = [](const vector<int>& nums) { long long sum = 0; long long zeros = 0; for (int x : nums) { sum += x; zeros += x == 0; } return pair{sum, zeros}; }; auto [s1, z1] = getSumAndZeros(nums1); auto [s2, z2] = getSumAndZeros(nums2); if (z1 == 0 && z2 == 0) { return s1 == s2 ? s1 : -1; } else if (z1 == 0) { return s2 + z2 <= s1 ? s1 : -1; } else if (z2 == 0) { return s1 + z1 <= s2 ? s2 : -1; } else { return max(s1 + z1, s2 + z2); } return -1; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment