Minimum Equal Sum of Two Arrays After Replacing Zeros

Minimum Equal Sum of Two Arrays After Replacing Zeros - Problem

Array Greedy Medium

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.

Input & Output

Example 1 — Basic Case with Zeros

$ Input: nums1 = [3,2,0,1,0], nums2 = [6,5,0]

› Output: 51

💡 Note: Replace zeros with 1: nums1 = [3,2,1,1,1] (sum=8), nums2 = [6,5,1] (sum=12). Since nums2 has higher sum and nums1 has more zeros, we can increase nums1's zeros to balance: nums1 = [3,2,1,1,5] gives sum=12. Answer is 12.

Example 2 — Impossible Case

$ Input: nums1 = [1,2], nums2 = [3,4]

› Output: -1

💡 Note: No zeros in either array. nums1 sum = 3, nums2 sum = 7. Since we can't change any values, it's impossible to make them equal.

Example 3 — One Array Without Zeros

$ Input: nums1 = [1,1,1,1], nums2 = [0,0,0,0]

› Output: 4

💡 Note: nums1 sum = 4 (no zeros), nums2 can be [1,1,1,1] with sum = 4. Both sums can be equal at 4.

Constraints

1 ≤ nums1.length, nums2.length ≤ 10⁵
0 ≤ nums1[i], nums2[i] ≤ 10⁶

Visualization

Tap to expand

Asked in

M Microsoft 15 a Amazon 12

The key insight is to replace all zeros with 1 (minimum positive value) and check if we can balance the sums. If one array has no zeros but a smaller sum, it's impossible. Otherwise, take the maximum of the two minimum sums. Best approach is greedy. Time: O(n+m), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(∞)	O(1)	Generate all possible combinations of positive integers for zeros
Greedy Approach	O(n + m)	O(1)	Replace all zeros with 1 (minimum positive) and check if balance is possible

Brute Force - Try All Combinations — Algorithm Steps

Generate all combinations of positive integers for zeros
Calculate sum for each combination
Find minimum equal sum across all valid combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Zeros

Identify all zero positions in both arrays

Try Values

For each zero, try values 1, 2, 3, ...

Check Equal

Find minimum equal sum across all combinations

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long solution(int* nums1, int size1, int* nums2, int size2) {
    long long sum1 = 0, sum2 = 0;
    int zeros1 = 0, zeros2 = 0;
    
    for (int i = 0; i < size1; i++) {
        if (nums1[i] == 0) {
            zeros1++;
            sum1 += 1;
        } else {
            sum1 += nums1[i];
        }
    }
    
    for (int i = 0; i < size2; i++) {
        if (nums2[i] == 0) {
            zeros2++;
            sum2 += 1;
        } else {
            sum2 += nums2[i];
        }
    }
    
    if (zeros1 == 0 && zeros2 == 0) {
        return sum1 == sum2 ? sum1 : -1;
    }
    if (zeros1 == 0 && sum1 < sum2) {
        return -1;
    }
    if (zeros2 == 0 && sum2 < sum1) {
        return -1;
    }
    
    return sum1 > sum2 ? sum1 : sum2;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums1[1000], size1 = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strcmp(token, "\n") != 0) {
            nums1[size1++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    fgets(line, sizeof(line), stdin);
    int nums2[1000], size2 = 0;
    token = strtok(line, "[,]");
    while (token != NULL) {
        if (strcmp(token, "\n") != 0) {
            nums2[size2++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%lld\n", solution(nums1, size1, nums2, size2));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(∞)

Infinite combinations of positive integers for each zero position

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for calculations

✓ Linear Space

18.5K Views

Medium Frequency

~25 min Avg. Time

486 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler