# Equal Sum Arrays With Minimum Number of Operations
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/equal-sum-arrays-with-minimum-number-of-operations)
Canonical: https://scaleengineer.com/dsa/problems/equal-sum-arrays-with-minimum-number-of-operations
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
**Companies:** [American Express](https://scaleengineer.com/companies/american-express)
---
## 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.

**Example 1:**

**Input:** nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]
**Output:** 3
**Explanation:** You can make the sums of nums1 and nums2 equal with 3 operations. All indices are 0-indexed.
- Change nums2[0] to 6. nums1 = [1,2,3,4,5,6], nums2 = [**6**,1,2,2,2,2].
- Change nums1[5] to 1. nums1 = [1,2,3,4,5,**1**], nums2 = [6,1,2,2,2,2].
- Change nums1[2] to 2. nums1 = [1,2,**2**,4,5,1], nums2 = [6,1,2,2,2,2].

**Example 2:**

**Input:** nums1 = [1,1,1,1,1,1,1], nums2 = [6]
**Output:** -1
**Explanation:** There is no way to decrease the sum of nums1 or to increase the sum of nums2 to make them equal.

**Example 3:**

**Input:** nums1 = [6,6], nums2 = [1]
**Output:** 3
**Explanation:** You can make the sums of nums1 and nums2 equal with 3 operations. All indices are 0-indexed. 
- Change nums1[0] to 2. nums1 = [**2**,6], nums2 = [1].
- Change nums1[1] to 2. nums1 = [2,**2**], nums2 = [1].
- Change nums2[0] to 4. nums1 = [2,2], nums2 = [**4**].

**Constraints:**

* `1 <= nums1.length, nums2.length <= 105`
* `1 <= nums1[i], nums2[i] <= 6`

# Approaches
## Greedy Approach with Sorting
This approach first calculates the difference between the sums of the two arrays. To minimize this difference with the fewest operations, we should always make the change that provides the largest reduction in the difference. The possible changes are decreasing an element in the larger-sum array to 1, or increasing an element in the smaller-sum array to 6. We can collect all such possible 'gains' (reductions in difference), sort them in descending order, and apply them one by one until the difference is covered.
**Time:** O(N log N), where N is the total number of elements (nums1.length + nums2.length). The dominant step is sorting the list of all possible gains. · **Space:** O(N), where N is the total number of elements (nums1.length + nums2.length). This space is used to store the list of gains.
**Pros:** Conceptually straightforward greedy logic.; Correctly finds the minimum number of operations.
**Cons:** The sorting step makes it less efficient than possible, with a time complexity of O(N log N).; Requires extra space proportional to the total number of elements to store the gains.
### Explanation
The core idea is to greedily reduce the difference between the two sums at each step. We first handle the edge case where it's impossible to make the sums equal. This occurs if the maximum possible sum of one array is less than the minimum possible sum of the other. For an array of length `n`, the sum is in the range `[n, 6*n]`. Thus, if `6 * n1 < n2` or `6 * n2 < n1`, we return -1.

Otherwise, we calculate the sums `sum1` and `sum2`. To simplify the logic, we can ensure `sum1` is always the larger sum by swapping the arrays if `sum1 < sum2`. The difference to eliminate is `diff = sum1 - sum2`.

To reduce `diff` in the minimum number of operations, we should always pick the operation that yields the maximum possible reduction. The possible reductions (gains) are:
1.  Changing an element `x` from `nums1` to 1, giving a gain of `x - 1`.
2.  Changing an element `y` from `nums2` to 6, giving a gain of `6 - y`.

We gather all these potential gains into a single list, sort it in descending order, and apply them greedily until `diff` is reduced to 0 or less. The number of gains applied gives the minimum number of operations.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int minOperations(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;

        if (n1 * 6 < n2 || n2 * 6 < n1) {
            return -1;
        }

        long sum1 = 0;
        for (int num : nums1) {
            sum1 += num;
        }
        long sum2 = 0;
        for (int num : nums2) {
            sum2 += num;
        }

        if (sum1 == sum2) {
            return 0;
        }

        if (sum1 < sum2) {
            // Swap to make sure nums1 has the larger sum
            return minOperations(nums2, nums1);
        }

        long diff = sum1 - sum2;
        List<Integer> gains = new ArrayList<>();
        for (int num : nums1) {
            gains.add(num - 1);
        }
        for (int num : nums2) {
            gains.add(6 - num);
        }

        Collections.sort(gains, Collections.reverseOrder());

        int operations = 0;
        for (int gain : gains) {
            diff -= gain;
            operations++;
            if (diff <= 0) {
                break;
            }
        }
        return operations;
    }
}
```
### Algorithm
- Check for impossibility: If `6 * nums1.length < nums2.length` or `6 * nums2.length < nums1.length`, return -1.
- Calculate `sum1` and `sum2`. If they are equal, return 0.
- To simplify, ensure `sum1` is the larger sum. If `sum1 < sum2`, swap the roles of the two arrays.
- Calculate the target difference `diff = sum1 - sum2`.
- Create a list to store all possible gains from one operation.
- For each `num` in the larger-sum array `nums1`, add a potential gain of `num - 1` to the list.
- For each `num` in the smaller-sum array `nums2`, add a potential gain of `6 - num` to the list.
- Sort the list of gains in descending order.
- Initialize `operations = 0`.
- Iterate through the sorted gains. For each `gain`:
-    Subtract the `gain` from `diff`.
-    Increment `operations`.
-    If `diff` is now less than or equal to 0, break the loop.
- Return the total `operations`.

## Optimized Greedy Approach with Counting
This approach improves upon the simple greedy strategy by leveraging the constraint that all numbers are between 1 and 6. Instead of creating a list of all possible gains and sorting it, we can use a frequency array to count the occurrences of each possible gain value. The possible gains are integers from 0 to 5. By iterating from the largest possible gain (5) down to the smallest (1), we can greedily reduce the sum difference in the most efficient way, thus avoiding the expensive sorting step.
**Time:** O(N), where N is the total number of elements (nums1.length + nums2.length). We iterate through the arrays once to calculate sums and populate the counts array, and then iterate through the fixed-size counts array. This is linear time. · **Space:** O(1), as the extra space used for the `counts` array is constant (size 6), regardless of the input array sizes.
**Pros:** Highly efficient with linear time complexity.; Uses constant extra space, making it very memory-efficient.; Optimal solution for this problem due to the constraints on element values.
**Cons:** The logic is slightly more complex than the sorting-based approach as it relies on the specific constraints of the problem.
### Explanation
This optimized approach avoids sorting by using a counting array, which is possible due to the small, fixed range of values (1-6) in the input arrays. The initial checks for impossibility and sum calculations are the same as the previous approach. We still ensure `sum1 >= sum2` to simplify logic.

The key optimization is how we handle the gains. Instead of a list, we use a `counts` array of size 6, where `counts[i]` stores the total number of times a gain of value `i` can be achieved. The possible gains range from 0 to 5.
- For an element `x` in the larger-sum array, changing it to 1 gives a gain of `x-1`.
- For an element `y` in the smaller-sum array, changing it to 6 gives a gain of `6-y`.

We populate the `counts` array by iterating through both `nums1` and `nums2` once. Then, to reduce the `diff`, we iterate from the largest gain `g = 5` down to 1. For each `g`, we use as many of these gains as needed (or available) to reduce `diff`. This greedy application of the largest available gains first ensures the minimum number of operations without needing to sort.

```java
class Solution {
    public int minOperations(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;

        if (n1 * 6 < n2 || n2 * 6 < n1) {
            return -1;
        }

        long sum1 = 0;
        for (int num : nums1) {
            sum1 += num;
        }
        long sum2 = 0;
        for (int num : nums2) {
            sum2 += num;
        }

        if (sum1 == sum2) {
            return 0;
        }

        if (sum1 < sum2) {
            // Swap to make sure nums1 has the larger sum
            return minOperations(nums2, nums1);
        }

        long diff = sum1 - sum2;
        int[] counts = new int[6]; // counts[i] stores frequency of gain i+1
        for (int num : nums1) {
            counts[num - 1]++;
        }
        for (int num : nums2) {
            counts[6 - num]++;
        }

        int operations = 0;
        for (int gain = 5; gain >= 1; gain--) {
            if (counts[gain] == 0) {
                continue;
            }
            
            int numAvailable = counts[gain];
            
            if (diff <= (long)gain * numAvailable) {
                operations += (int)((diff + gain - 1) / gain); // Ceiling division
                return operations;
            }
            
            diff -= (long)gain * numAvailable;
            operations += numAvailable;
        }

        return operations;
    }
}
```
### Algorithm
- Check for impossibility: If `6 * nums1.length < nums2.length` or `6 * nums2.length < nums1.length`, return -1.
- Calculate `sum1` and `sum2`. If they are equal, return 0.
- To simplify, ensure `sum1` is the larger sum. If `sum1 < sum2`, swap the roles of the two arrays (a recursive call with swapped arguments is a clean way to do this).
- Calculate the target difference `diff = sum1 - sum2`.
- Create a frequency array `counts` of size 6. `counts[i]` will store the number of available operations that yield a gain of `i`.
- Populate `counts`: For each `num` in the larger-sum array `nums1`, increment `counts[num - 1]`. For each `num` in the smaller-sum array `nums2`, increment `counts[6 - num]`.
- Initialize `operations = 0`.
- Iterate through possible gains from largest to smallest (from `gain = 5` down to 1).
- For each `gain` value, check if it can cover the remaining `diff`.
- If `diff <= gain * counts[gain]`, calculate the minimum operations of this `gain` value needed (`ceil(diff / gain)`), add it to the total `operations`, and return the result.
- If not, use all available operations of this `gain` value. Add `counts[gain]` to `operations` and decrease `diff` by `gain * counts[gain]`.
- After the loop, return the total `operations`.

# Solutions
### Java

```java
class Solution { public int minOperations ( int [] nums1 , int [] nums2 ) { int s1 = Arrays . stream ( nums1 ). sum (); int s2 = Arrays . stream ( nums2 ). sum (); if ( s1 == s2 ) { return 0 ; } if ( s1 > s2 ) { return minOperations ( nums2 , nums1 ); } int d = s2 - s1 ; int [] arr = new int [ nums1 . length + nums2 . length ]; int k = 0 ; for ( int v : nums1 ) { arr [ k ++] = 6 - v ; } for ( int v : nums2 ) { arr [ k ++] = v - 1 ; } Arrays . sort ( arr ); for ( int i = 1 , j = arr . length - 1 ; j >= 0 ; ++ i , -- j ) { d -= arr [ j ]; if ( d <= 0 ) { return i ; } } return - 1 ; } }
```

### CPP

```cpp
class Solution { public: int minOperations ( vector < int >& nums1 , vector < int >& nums2 ) { int s1 = accumulate ( nums1 . begin (), nums1 . end (), 0 ); int s2 = accumulate ( nums2 . begin (), nums2 . end (), 0 ); if ( s1 == s2 ) return 0 ; if ( s1 > s2 ) return minOperations ( nums2 , nums1 ); int d = s2 - s1 ; int arr [ nums1 . size () + nums2 . size ()]; int k = 0 ; for ( int & v : nums1 ) arr [ k ++ ] = 6 - v ; for ( int & v : nums2 ) arr [ k ++ ] = v - 1 ; sort ( arr , arr + k , greater <> ()); for ( int i = 0 ; i < k ; ++ i ) { d -= arr [ i ]; if ( d <= 0 ) return i + 1 ; } return - 1 ; } };
```

### Python

```python
class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int: s1, s2 = sum(nums1), sum(nums2) if s1 == s2: return 0 if s1 > s2: return self . minOperations(nums2, nums1) arr = [6 - v for v in nums1] + [v - 1 for v in nums2] d = s2 - s1 for i, v in enumerate(sorted(arr, reverse=True), 1): d -= v if d <= 0: return i return - 1

```