2918. Minimum Equal Sum of Two Arrays After Replacing Zeros
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
Solutions
Solution 1: Case Analysis
We consider the case where we treat all $0$s in the array as $1$s, and calculate the sum of the two arrays separately, denoted as $s_1$ and $s_2$. Without loss of generality, we assume that $s_1 \le s_2$.
- If $s_1 = s_2$, then the answer is $s_1$.
- If $s_1 \lt s_2$, then there must exist a $0$ in $nums1$ to make the sum of the two arrays equal. In this case, the answer is $s_2$. Otherwise, it means that it is impossible to make the sum of the two arrays equal, and we return $-1$.
The time complexity is $O(n + m)$, where $n$ and $m$ are the lengths of the arrays $nums1$ and $nums2$, respectively. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 |