Description
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
Python3
class Solution:
def minSum(self, nums1: List[int], nums2: List[int]) -> int:
s1 = sum(nums1)
s2 = sum(nums2)
zeroes1, zeroes2 = nums1.count(0), nums2.count(0)
if zeroes1 == 0 and zeroes2 == 0:
return s1 if s1 == s2 else -1
if zeroes1 == 0:
return s1 if s2 + zeroes2 <= s1 else -1
if zeroes2 == 0:
return s2 if s1 + zeroes1 <= s2 else -1
def good(k):
return s1 + zeroes1 <= k and s2 + zeroes2 <= k
left, right = -1, 10 ** 30 + 1
res = -1
while left < right:
mid = left + (right - left) // 2
if good(mid):
res = mid
right = mid
else:
left = mid + 1
return res