1775. Equal Sum Arrays With Minimum Number of Operations

Description

You are given two arrays of integers nums1 and , 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

 

Solutions

Solution: Greedy

• Time complexity: O(nlogn)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
const minOperations = function (nums1, nums2) {
  const size1 = nums1.length;
  const size2 = nums2.length;
  if (size1 * 6 < size2 || size1 > size2 * 6) return -1;

  const sum1 = nums1.reduce((sum, num) => sum + num);
  const sum2 = nums2.reduce((sum, num) => sum + num);
  const operations = (a, b) => {
    let left = (result = 0);
    let right = b.nums.length - 1;

    while (a.sum < b.sum) {
      right < 0 || (left < a.nums.length && 6 - a.nums[left] > b.nums[right] - 1)
        ? (a.sum += 6 - a.nums[left++])
        : (b.sum -= b.nums[right--] - 1);

      result += 1;
    }
    return result;
  };

  nums1.sort((a, b) => a - b);
  nums2.sort((a, b) => a - b);
  return sum1 < sum2
    ? operations({ nums: nums1, sum: sum1 }, { nums: nums2, sum: sum2 })
    : operations({ nums: nums2, sum: sum2 }, { nums: nums1, sum: sum1 });
};