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.

&nbsp;
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].


&nbsp;
Constraints:


	1 &lt;= nums1.length, nums2.length &lt;= 105
	1 &lt;= nums1[i], nums2[i] &lt;= 6


class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
        
		# step1. determine the larger array and the smaller array, and get the difference on sum
        sum1 = sum(nums1)
        sum2 = sum(nums2)
        
        if sum1==sum2:
            return 0
        elif sum1>sum2:
            larger_sum_nums = nums1
            smaller_sum_nums = nums2
        else:
            larger_sum_nums = nums2
            smaller_sum_nums = nums1
		
        sum_diff = abs(sum1-sum2)
            
        # step2. calculate the max "gain" at each position (how much difference we can reduce if operating on that position)    
        gains_in_larger_array = [num-1 for num in larger_sum_nums]
        gains_in_smaller_array = [6-num for num in smaller_sum_nums]
        
		# step3. sort the "gain" and check the least number of steps to reduce the difference to 0
        gains = gains_in_larger_array + gains_in_smaller_array
        gains.sort(reverse = True)
        
        count = 0
        target_diff = sum_diff
        
        for i in range(len(gains)):
            target_diff -= gains[i]
            count += 1
            
            if target_diff <= 0:
                return count
		
		# return -1 if the difference still cannot be reduced to 0 even after operating on all positions
        return -1
class Solution {
    public int minOperations(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        if (m > 6 * n || n > 6 * m) return -1;

        int sum1 = 0, sum2 = 0;
        for (int i : nums1) sum1 += i;
        for (int i : nums2) sum2 += i;

        int diff = sum1 - sum2;
        if (diff == 0) return 0;

        return (diff > 0 ? helper(nums1, nums2, diff)
                         : helper(nums2, nums1, -diff));
    }

    private int helper(int[] nums1, int[] nums2, int diff) {
        // count[i] : frequency of numbers that can reduce the diff by i
        int[] count = new int[6];
        for (int num : nums1) count[num - 1]++;
        for (int num : nums2) count[6 - num]++;

        int res = 0;
        for (int i = 5; i > 0; i--) {
            int c = Math.min(count[i], diff / i + (diff % i == 0 ? 0 : 1));

            res += c;
            diff -= c * i;

            if (diff <= 0) break;
        }
        return res;
    }
}
/**
 * @brief
 * Given two array, return the minimum numbers we have to change the values to make two arrays sum equal
 *
 * [Observation]
 * Since the value is from 1 ~ 6
 *
 * Min sum of the array = len(arr)
 * Max sum of the array = 6 len(arr)
 *
 * When to arrays range cannot overlap -> no answer
 *
 * If there is a answer -> sum s, value will be between s1 and s2
 * So, let's say if s1 is smaller, we would like to increase s1's element and decrease s2's element
 * -> We only have to design for s1 is smaller than s2.
 *
 * [Key] Which element's should we increase and decrease?
 * To minimize the changing elements, we change the number who can mostly decrease the differences.
 * So, we compare the smallest element in num1 and largest in num2.
 * -> sorting
 *
 * @algo sorting + greedy
 * Time O(NlogN) for sorting
 * Space O(1)
 */
class Solution {
public:
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        int l1 = nums1.size(); // l1 ~ 6l1
        int l2 = nums2.size(); // l2 ~ 6l2

        if(6*l1 < l2 || 6*l2 < l1) {
            return -1;
        }

        int sum1 = accumulate(nums1.begin(), nums1.end(), 0);
        int sum2 = accumulate(nums2.begin(), nums2.end(), 0);
        if(sum1 > sum2) return minOperations(nums2, nums1);

        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end(), greater<int>());
        // let us design the way where sum1 <= sum2
        int ans = 0, ptr1 = 0, ptr2 = 0;
        int diff = sum2 - sum1;

        while(diff > 0) {
            if(ptr2 == l2 || ptr1 < l1 && (6 - nums1[ptr1]) >= (nums2[ptr2] - 1)) {
                diff -= (6 - nums1[ptr1]);
                ans++;
                ptr1++;
            }
            else {
                diff -= (nums2[ptr2] - 1);
                ans++;
                ptr2++;
            }
        }
        return ans;
    }
};
var minOperations = function(nums1, nums2) {
    /*
    Two impossible cases:
    min1...max1 ... min2...max2 -> we can't make them equal
    min2...max2 ... min1...max1 -> we can't make them equal
    */
    let min1 = nums1.length * 1;
    let max1 = nums1.length * 6;
    let min2 = nums2.length * 1;
    let max2 = nums2.length * 6;
    if (min2 > max1 || min1 > max2) {
        return -1;
    }
    let sum1 = nums1.reduce((acc,cur) => acc + cur);
    let sum2 = nums2.reduce((acc,cur) => acc + cur);
    if (sum1 === sum2) return 0;
    if (sum1 < sum2) {
        return helper(nums1, nums2, sum1, sum2);
    } else {
        return helper(nums2, nums1, sum2, sum1);
    }
    // T.C: O(M + N), M = # of nums1, N = # of nums2
    // S.C: O(1)
};

// Condition: sum of A < sum of B
// the idea is to add the maximum possible value to sumA and
// subtract the maximum possible value from sumB so that
// we make sumA >= sumB as soon as possible
function helper(A, B, sumA, sumB) {
    let freqA = new Array(7).fill(0);
    let freqB = new Array(7).fill(0);
    for (let i = 0; i < A.length; i++) {
        freqA[A[i]]++;
    }
    for (let i = 0; i < B.length; i++) {
        freqB[B[i]]++;
    }
    let count = 0;
    for (let i = 1; i <= 6; i++) {
        // increase sumA
        while (freqA[i] > 0 && sumA < sumB) {
            sumA += 6-i;
            freqA[i]--;
            count++;
        }
        let j = 7-i;
        // decrease sumB
        while (freqB[j] > 0 && sumA < sumB) {
            sumB -= j-1;
            freqB[j]--;
            count++;
        }
        if (sumA >= sumB) break;
    }
    return count;
}
Equal Sum Arrays With Minimum Number of Operations