Skip to content

1775. Equal Sum Arrays With Minimum Number of Operations 👍

  • Time: $O(|\texttt{nums1}| + |\texttt{nums2}|)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  int minOperations(vector<int>& nums1, vector<int>& nums2) {
    if (nums1.size() * 6 < nums2.size() || nums2.size() * 6 < nums1.size())
      return -1;

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

    int ans = 0;
    // increases in nums1 & decreases in nums2
    vector<int> count(6);

    for (const int num : nums1)
      ++count[6 - num];

    for (const int num : nums2)
      ++count[num - 1];

    for (int i = 5; sum2 > sum1;) {
      while (count[i] == 0)
        --i;
      sum1 += i;
      --count[i];
      ++ans;
    }

    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  public int minOperations(int[] nums1, int[] nums2) {
    if (nums1.length * 6 < nums2.length || nums2.length * 6 < nums1.length)
      return -1;

    int sum1 = Arrays.stream(nums1).sum();
    int sum2 = Arrays.stream(nums2).sum();
    if (sum1 > sum2)
      return minOperations(nums2, nums1);

    int ans = 0;
    // increases in nums1 & decreases in nums2
    int[] count = new int[6];

    Arrays.stream(nums1).forEach(num -> ++count[6 - num]);
    Arrays.stream(nums2).forEach(num -> ++count[num - 1]);

    for (int i = 5; sum2 > sum1;) {
      while (count[i] == 0)
        --i;
      sum1 += i;
      --count[i];
      ++ans;
    }

    return ans;
  }
}