Minimum equal sum

Minimum Equal Sum – Matching Arrays with Smart Replacements

Problem Statement

You are given two integer arrays nums1 and nums2, which may contain zeros. You must replace each 0 with a strictly positive integer (≥ 1) such that the sum of both arrays becomes equal.

Your goal is to minimize that common equal sum after all replacements. If there is no way to make the sums equal with any valid replacements, return -1.

Example

Input:

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

Output:

12

Explanation:

Replace the two zeros in nums1 with 2 and 4 → [3,2,2,1,4]
Replace the zero in nums2 with 1 → [6,5,1]
Both arrays now sum to 12.

Best Data Structure for the Job

This problem is mostly numerical, so there’s no need for complex data structures like trees or heaps.
What you do need is:

• A way to count zeros and compute current sums.

• Simple math to determine possible ranges.

• Long data type to handle large sums.

Different Approaches

Approach 1: Brute Force (Try All Possible Target Sums)

We simulate all possible sums from the maximum of the minimum achievable sums of both arrays to the minimum of the maximum achievable sums. For each possible target, we check if it can be reached by replacing the zeros.

class Solution {
    public long minSum(int[] nums1, int[] nums2) {
        int zeros1 = 0, zeros2 = 0;
        long sum1 = 0, sum2 = 0;
        
        for (int num : nums1) {
            if (num == 0) zeros1++;
            else sum1 += num;
        }
        
        for (int num : nums2) {
            if (num == 0) zeros2++;
            else sum2 += num;
        }

        long minPossible1 = sum1 + zeros1;
        long maxPossible1 = sum1 + zeros1 * 1_000_000L;
        long minPossible2 = sum2 + zeros2;
        long maxPossible2 = sum2 + zeros2 * 1_000_000L;

        long low = Math.max(minPossible1, minPossible2);
        long high = Math.min(maxPossible1, maxPossible2);

        for (long target = low; target <= high; target++) {
            long need1 = target - sum1;
            long need2 = target - sum2;

            if (need1 >= zeros1 && need1 <= zeros1 * 1_000_000L &&
                need2 >= zeros2 && need2 <= zeros2 * 1_000_000L) {
                return target;
            }
        }

        return -1;
    }
}

This approach works fine for small ranges, but it becomes inefficient for large numbers of zeros.

Approach 2: Optimized Math-Based Solution

Instead of looping through possible sums, we compute the valid sum range for both arrays and return the smallest sum where the ranges overlap.

class Solution {
    public long minSum(int[] nums1, int[] nums2) {
        long sum1 = 0, sum2 = 0;
        long zeros1 = 0, zeros2 = 0;

        for (int n : nums1) {
            if (n == 0) zeros1++;
            else sum1 += n;
        }

        for (int n : nums2) {
            if (n == 0) zeros2++;
            else sum2 += n;
        }

        long minSum1 = sum1 + zeros1; // all 0s replaced with 1
        long maxSum1 = sum1 + zeros1 * 1_000_000L;

        long minSum2 = sum2 + zeros2;
        long maxSum2 = sum2 + zeros2 * 1_000_000L;

        long target = Math.max(minSum1, minSum2);

        if (target > maxSum1 || target > maxSum2) return -1;

        return target;
    }
}

⚠️ Common Mistakes and Pitfalls

• Forgetting positive replacements: Replacements must be strictly positive (≥ 1), not zero.

• Integer overflow: If you’re summing large numbers, especially after replacements, use long instead of int.

• Missing range overlap check: Don't assume sums can always be matched just because there are zeros.

• Incorrect lower bound: You must add the minimum (1 per zero), not zero.

📊 Time and Space Complexity Analysis

Approach	Time Complexity	Space Complexity
Brute Force	O(range)	O(1)
Optimized Math	O(n + m)	O(1)

🌍 Real-world Applications

• Budget Allocation: Distributing pending (zero) entries in two departments’ budgets so both totals match.

• Score Normalization: Filling in missing data such that different teams achieve equal aggregate scores.

• Data Imputation: Adjusting missing values to balance out datasets in machine learning.

• Game Mechanics: Assigning minimum possible scores to players with undefined values to reach a fair match.

I hope you found this article insightful! Keep exploring, keep learning, and don’t forget to check back daily for more exciting problem breakdowns. If you know someone who would benefit from this, share it with them and help them grow too! That’s it for today—see you in the next post!

                                                                                                                                         Signing off!! 

                                                                                                Master DSA One Problem at a Time :)