Minimum Equal Sum of Two Arrays After Replacing Zeros
Problem
Given two arrays nums1 and nums2 of positive integers, replace every 0 in both arrays with a strictly positive integer so the two arrays end up with an equal sum. Return the minimum such equal sum, or -1 if it is impossible.
Each zero must become at least 1, so the smallest sum a side can reach is its current sum plus its count of zeros. A side with no zeros is locked at its current sum and cannot grow.
nums1 = [3,2,0,1,0], nums2 = [6,5,0]12def minSum(nums1, nums2):
# sum and zero-count of each array
sum1 = sum(nums1); zero1 = nums1.count(0)
sum2 = sum(nums2); zero2 = nums2.count(0)
# each 0 must become >= 1, so the smallest reachable sum is sum + zeros
low1 = sum1 + zero1
low2 = sum2 + zero2
# a side with no zeros is fixed; if it must still grow, it is impossible
if zero1 == 0 and low1 < low2:
return -1
if zero2 == 0 and low2 < low1:
return -1
# otherwise lift the smaller side up to the larger floor
return max(low1, low2)function minSum(nums1, nums2) {
// sum and zero-count of each array
let sum1 = 0, zero1 = 0, sum2 = 0, zero2 = 0;
for (const v of nums1) { sum1 += v; if (v === 0) zero1++; }
for (const v of nums2) { sum2 += v; if (v === 0) zero2++; }
// each 0 must become >= 1, so the smallest reachable sum is sum + zeros
const low1 = sum1 + zero1;
const low2 = sum2 + zero2;
// a side with no zeros is fixed; if it must still grow, it is impossible
if (zero1 === 0 && low1 < low2) return -1;
if (zero2 === 0 && low2 < low1) return -1;
// otherwise lift the smaller side up to the larger floor
return Math.max(low1, low2);
}long minSum(int[] nums1, int[] nums2) {
// sum and zero-count of each array
long sum1 = 0, sum2 = 0;
int zero1 = 0, zero2 = 0;
for (int v : nums1) { sum1 += v; if (v == 0) zero1++; }
for (int v : nums2) { sum2 += v; if (v == 0) zero2++; }
// each 0 must become >= 1, so the smallest reachable sum is sum + zeros
long low1 = sum1 + zero1;
long low2 = sum2 + zero2;
// a side with no zeros is fixed; if it must still grow, it is impossible
if (zero1 == 0 && low1 < low2) return -1;
if (zero2 == 0 && low2 < low1) return -1;
// otherwise lift the smaller side up to the larger floor
return Math.max(low1, low2);
}long long minSum(vector<int>& nums1, vector<int>& nums2) {
// sum and zero-count of each array
long long sum1 = 0, sum2 = 0;
int zero1 = 0, zero2 = 0;
for (int v : nums1) { sum1 += v; if (v == 0) zero1++; }
for (int v : nums2) { sum2 += v; if (v == 0) zero2++; }
// each 0 must become >= 1, so the smallest reachable sum is sum + zeros
long long low1 = sum1 + zero1;
long long low2 = sum2 + zero2;
// a side with no zeros is fixed; if it must still grow, it is impossible
if (zero1 == 0 && low1 < low2) return -1;
if (zero2 == 0 && low2 < low1) return -1;
// otherwise lift the smaller side up to the larger floor
return max(low1, low2);
}Explanation
This is a greedy / math problem. Replacing a zero with the smallest legal value (a 1) is always the cheapest move, so the minimum reachable sum of each array is its current sum plus its number of zeros. Call these floors low1 and low2.
Any remaining gap can be absorbed by one of the zeros: if a side still has a zero left over, we can grow that single replacement by any amount, so a side with at least one zero can reach any sum from its floor upward.
So the smallest common sum is simply max(low1, low2) — push the array with the smaller floor up to meet the larger floor. The other array is already there.
The only failure case is when the side that needs to grow has no zeros: it is frozen at its sum and can never reach the other floor. Concretely, if zero1 == 0 and low1 < low2 (or the symmetric case), the answer is -1.
Example: nums1 = [3,2,0,1,0] has sum 6 and two zeros → floor 8; nums2 = [6,5,0] has sum 11 and one zero → floor 12. Both sides have zeros, so the answer is max(8, 12) = 12. For nums1 = [2,0,2,0] (floor 6) and nums2 = [1,4] (floor 5, no zeros), nums2 is frozen below 6, so it is impossible → -1.