Equal Sum Arrays With Minimum Number of Operations

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:


Solution:

always try to increase the smallest number of decrease the largest number

class Solution {
    public int minOperations(int[] nums1, int[] nums2) {
        // num1: min: 6, max: 36, curr: 21
        // num2: min: 6, max: 36, curr: 10
        int m = nums1.length, n = nums2.length;
        int sum1 = 0, sum2 = 0;
        int[] count1 = new int[7];
        int[] count2 = new int[7];
        for (int v : nums1) {
            count1[v] ++;
            sum1 += v;
        }
        for (int v : nums2) {
            count2[v] ++;
            sum2 += v;
        }
        if (sum1 == sum2) return 0;
        if (sum1 > sum2) {
            int min1 = m;
            int max2 = n * 6;
            if (min1 > max2) return -1;
            return minOp(count1, count2, sum1 - sum2);
        } else {
            int min2 = n;
            int max1 = m * 6;
            if (min2 > max1) return -1;
            return minOp(count2, count1, sum2 - sum1);
        }
    }
    
    // decrease countb, increase counts
    private int minOp(int[] countB, int[] countS, int steps) {
        // System.out.println(Arrays.toString(countB) + ", " + Arrays.toString(countS) + ", " + steps);
        int op = 0;
        int step = 0;
        outer:
        for (int i = 1; i <= 6 && step < steps; i ++) {
            while (countB[7 - i] > 0) {
                countB[7 - i] --;
                step += 7 - i - 1;
                op ++;
                // System.out.println(Arrays.toString(countB) + ", " + Arrays.toString(countS) + ", " + step);
                if (step >= steps) break outer;
            }
            while (countS[i] > 0) {
                countS[i] --;
                step += 6 - i;
                op ++;
                // System.out.println(Arrays.toString(countB) + ", " + Arrays.toString(countS) + ", " + step);
                if (step >= steps) break outer;
            }
        }
        return op;
    }
}