Equal Sum Arrays With Minimum Number of Operations

Equal Sum Arrays With Minimum Number of Operations - Problem

You are given two arrays of integers nums1 and nums2, possibly of different lengths. The values in the arrays are between 1 and 6, inclusive.

In one operation, you can change any integer's value in any of the arrays to any value between 1 and 6, inclusive.

Return the minimum number of operations required to make the sum of values in nums1 equal to the sum of values in nums2. Return -1 if it is not possible to make the sum of the two arrays equal.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: Sum of nums1 is 21, sum of nums2 is 10. We need to reduce difference of 11. Change nums1[4] from 5→1 (gain 4), nums1[3] from 4→1 (gain 3), nums1[2] from 3→1 (gain 2). Total gain = 9. Change nums2[0] from 1→3 (gain 2). Total operations = 4, but we only need 3 to reduce difference to 0.

Example 2 — Equal Sums

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

› Output: 1

💡 Note: Sum of nums1 is 7, sum of nums2 is 6. Difference is 1. Change any element in nums1 from 1→0 is invalid, but change nums2[0] from 6→7 is invalid too. Actually, change nums1[0] from 1→2 reduces difference by -1, making sums equal. Wait, let me recalculate: change nums2[0] from 6→7 isn't valid since max is 6. Change nums1[6] from 1→0 isn't valid since min is 1. We can change nums2[0] from 6→5 (reduces sum by 1) or change nums1 element from 1→2 (increases sum by 1). Either takes 1 operation.

Example 3 — Impossible Case

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

› Output: -1

💡 Note: nums1 sum is 12, nums2 sum is 1. Maximum possible sum for nums2 is 1×6=6, minimum possible sum for nums1 is 2×1=2. Since max of nums2 (6) < min of nums1 (2), it's impossible to equalize.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two arrays with different sums, elements range 1-6

Calculate Strategy

Find which changes give maximum impact

Apply Changes

Minimum operations to equalize sums

Key Takeaway

🎯 Key Insight: Greedily prioritize changes that provide maximum reduction in sum difference

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to greedily prioritize changes that provide maximum impact in reducing the sum difference. Calculate potential gains from each element change and apply the most beneficial changes first. Greedy approach works optimally here. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(6^n)	O(1)	Try all possible ways to change elements and find minimum operations
Greedy - Maximize Impact	O(n log n)	O(n)	Greedily change elements that provide maximum sum adjustment

Brute Force - Try All Combinations — Algorithm Steps

Calculate initial sum difference
Try all possible element changes
For each combination, count operations needed
Return minimum operations found

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Arrays with different sums

Try Changes

Recursively try changing each element to values 1-6

Find Minimum

Return minimum operations to equalize sums

Code -

solution.c — C

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

int backtrack(int* nums1, int n1, int* nums2, int n2, int idx1, int idx2, 
              int currentSum1, int currentSum2, int operations) {
    if (idx1 == n1 && idx2 == n2) {
        return currentSum1 == currentSum2 ? operations : INT_MAX;
    }
    
    if (idx1 < n1) {
        int minOps = INT_MAX;
        for (int val = 1; val <= 6; val++) {
            int ops = operations + (val != nums1[idx1] ? 1 : 0);
            int result = backtrack(nums1, n1, nums2, n2, idx1 + 1, idx2, 
                                 currentSum1 - nums1[idx1] + val, currentSum2, ops);
            if (result < minOps) minOps = result;
        }
        return minOps;
    } else {
        int minOps = INT_MAX;
        for (int val = 1; val <= 6; val++) {
            int ops = operations + (val != nums2[idx2] ? 1 : 0);
            int result = backtrack(nums1, n1, nums2, n2, idx1, idx2 + 1, 
                                 currentSum1, currentSum2 - nums2[idx2] + val, ops);
            if (result < minOps) minOps = result;
        }
        return minOps;
    }
}

int solution(int* nums1, int n1, int* nums2, int n2) {
    int sum1 = 0, sum2 = 0;
    for (int i = 0; i < n1; i++) sum1 += nums1[i];
    for (int i = 0; i < n2; i++) sum2 += nums2[i];
    
    if (sum1 == sum2) return 0;
    
    int minSum1 = n1, maxSum1 = n1 * 6;
    int minSum2 = n2, maxSum2 = n2 * 6;
    
    if (maxSum1 < minSum2 || minSum1 > maxSum2) return -1;
    
    int result = backtrack(nums1, n1, nums2, n2, 0, 0, sum1, sum2, 0);
    return result == INT_MAX ? -1 : result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse nums1
    int nums1[100], n1 = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums1[n1++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    
    // Parse nums2
    int nums2[100], n2 = 0;
    token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums2[n2++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums1, n1, nums2, n2));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(6^n)

Each element can be changed to 6 possible values, trying all combinations

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

850 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