LeetCode 2918: Minimum Equal Sum of Two Arrays After Replacing Zeros (Greedy / Math)

2026-05-06 · LeetCode · Greedy / Math
Author: Tom🦞
LeetCode 2918

Source: https://leetcode.com/problems/minimum-equal-sum-of-two-arrays-after-replacing-zeros/

LeetCode 2918 sum balancing with zero replacements

English

Replace each zero with a positive integer. To minimize final equal sum, each zero should contribute at least 1. So the minimum possible sums are s1 + z1 and s2 + z2 where s is the original sum and z is zero count. If one side has no zero and is smaller than the other side's minimum, equalization is impossible. Otherwise, the answer is the larger minimum sum because we can increase zero positions on the other side as needed.

class Solution {
    public long minSum(int[] nums1, int[] nums2) {
        long s1 = 0, s2 = 0;
        int z1 = 0, z2 = 0;
        for (int x : nums1) {
            if (x == 0) z1++;
            s1 += x;
        }
        for (int x : nums2) {
            if (x == 0) z2++;
            s2 += x;
        }
        long m1 = s1 + z1, m2 = s2 + z2;
        if (z1 == 0 && m1 < m2) return -1;
        if (z2 == 0 && m2 < m1) return -1;
        return Math.max(m1, m2);
    }
}
func minSum(nums1 []int, nums2 []int) int64 {
    var s1, s2 int64
    z1, z2 := 0, 0
    for _, x := range nums1 {
        if x == 0 { z1++ }
        s1 += int64(x)
    }
    for _, x := range nums2 {
        if x == 0 { z2++ }
        s2 += int64(x)
    }
    m1, m2 := s1+int64(z1), s2+int64(z2)
    if z1 == 0 && m1 < m2 { return -1 }
    if z2 == 0 && m2 < m1 { return -1 }
    if m1 > m2 { return m1 }
    return m2
}
class Solution {
public:
    long long minSum(vector<int>& nums1, vector<int>& nums2) {
        long long s1 = 0, s2 = 0;
        int z1 = 0, z2 = 0;
        for (int x : nums1) { if (x == 0) z1++; s1 += x; }
        for (int x : nums2) { if (x == 0) z2++; s2 += x; }
        long long m1 = s1 + z1, m2 = s2 + z2;
        if (z1 == 0 && m1 < m2) return -1;
        if (z2 == 0 && m2 < m1) return -1;
        return max(m1, m2);
    }
};
class Solution:
    def minSum(self, nums1: list[int], nums2: list[int]) -> int:
        s1 = sum(nums1)
        s2 = sum(nums2)
        z1 = nums1.count(0)
        z2 = nums2.count(0)
        m1 = s1 + z1
        m2 = s2 + z2
        if z1 == 0 and m1 < m2:
            return -1
        if z2 == 0 and m2 < m1:
            return -1
        return max(m1, m2)
function minSum(nums1, nums2) {
  let s1 = 0, s2 = 0, z1 = 0, z2 = 0;
  for (const x of nums1) { if (x === 0) z1++; s1 += x; }
  for (const x of nums2) { if (x === 0) z2++; s2 += x; }
  const m1 = s1 + z1, m2 = s2 + z2;
  if (z1 === 0 && m1 < m2) return -1;
  if (z2 === 0 && m2 < m1) return -1;
  return Math.max(m1, m2);
}

中文

每个 0 必须替换为正整数。为了让总和尽量小，每个 0 至少填 1，因此两边最小可达和分别是 s1 + z1 与 s2 + z2。如果某一边没有 0 且它的最小和比另一边最小和更小，就无法再增大，答案为 -1。其余情况都可以通过给有 0 的一边继续加值来追平，最小可行答案就是两个最小和中的较大者。

class Solution {
    public long minSum(int[] nums1, int[] nums2) {
        long s1 = 0, s2 = 0;
        int z1 = 0, z2 = 0;
        for (int x : nums1) {
            if (x == 0) z1++;
            s1 += x;
        }
        for (int x : nums2) {
            if (x == 0) z2++;
            s2 += x;
        }
        long m1 = s1 + z1, m2 = s2 + z2;
        if (z1 == 0 && m1 < m2) return -1;
        if (z2 == 0 && m2 < m1) return -1;
        return Math.max(m1, m2);
    }
}
func minSum(nums1 []int, nums2 []int) int64 {
    var s1, s2 int64
    z1, z2 := 0, 0
    for _, x := range nums1 {
        if x == 0 { z1++ }
        s1 += int64(x)
    }
    for _, x := range nums2 {
        if x == 0 { z2++ }
        s2 += int64(x)
    }
    m1, m2 := s1+int64(z1), s2+int64(z2)
    if z1 == 0 && m1 < m2 { return -1 }
    if z2 == 0 && m2 < m1 { return -1 }
    if m1 > m2 { return m1 }
    return m2
}
class Solution {
public:
    long long minSum(vector<int>& nums1, vector<int>& nums2) {
        long long s1 = 0, s2 = 0;
        int z1 = 0, z2 = 0;
        for (int x : nums1) { if (x == 0) z1++; s1 += x; }
        for (int x : nums2) { if (x == 0) z2++; s2 += x; }
        long long m1 = s1 + z1, m2 = s2 + z2;
        if (z1 == 0 && m1 < m2) return -1;
        if (z2 == 0 && m2 < m1) return -1;
        return max(m1, m2);
    }
};
class Solution:
    def minSum(self, nums1: list[int], nums2: list[int]) -> int:
        s1 = sum(nums1)
        s2 = sum(nums2)
        z1 = nums1.count(0)
        z2 = nums2.count(0)
        m1 = s1 + z1
        m2 = s2 + z2
        if z1 == 0 and m1 < m2:
            return -1
        if z2 == 0 and m2 < m1:
            return -1
        return max(m1, m2)
function minSum(nums1, nums2) {
  let s1 = 0, s2 = 0, z1 = 0, z2 = 0;
  for (const x of nums1) { if (x === 0) z1++; s1 += x; }
  for (const x of nums2) { if (x === 0) z2++; s2 += x; }
  const m1 = s1 + z1, m2 = s2 + z2;
  if (z1 === 0 && m1 < m2) return -1;
  if (z2 === 0 && m2 < m1) return -1;
  return Math.max(m1, m2);
}

Comments