Skip to content

← leetcode

Minimum Equal Sum of Two Arrays After Replacing Zeros

· Medium

LeetCode problem 2918

This question a fake medium or what?!

You can basically reduce the original question to:

If you change all the 0s present in both arrays to 1s and sum the elements of both arrays, which array has a larger sum?

Then, add on a follow-up question:

Given that you know which array has the LARGER sum after changing all the 0s present to 1s, does the array with the SMALLER sum have any 0s present in its INITIAL STATE?

Finally, after answering this question:

  • if yes, then we simply return the maximum of both arrays (with all the 0s converted to 1s)
  • if no, then we can simply return -1

This is because, we are allowed to change all the 0s to ANY STRICTLY POSITIVE NUMBER, meaning the minimum sum we can possibly find has to occur when all 0s are swapped to 1s.

Therefore that implies that if the smaller sum has no 0s present, it is simply impossible to set both sums to be equal.

code

class Solution {
public:
    long long minSum(vector<int>& nums1, vector<int>& nums2) {
        long long sum1 = 0, sum2 = 0;
        int count1 = 0, count2 = 0;
        for (int& num : nums1) {
            sum1 += num;
            if (num == 0) ++count1;
        }
        for (int& num : nums2) {
            sum2 += num;
            if (num == 0) ++count2;
        }

        if (sum1 + count1 > sum2 + count2 && count2 == 0) {
            return -1;
        } else if (sum1 + count1 < sum2 + count2 && count1 == 0) {
            return -1;
        }
        return max(sum1 + count1, sum2 + count2);
    }
};

complexity

  • Time: O(n+m) where n is the size of the array nums1 and m is the size of the array nums2
  • Space: O(1)

time taken

  • 4 minutes and 57 seconds