Equal Sum Arrays With Minimum Number of Operations LeetCode solution in C++

1
/**
2
 * @brief
3
 * Given two array, return the minimum numbers we have to change the values to
4
 * make two arrays sum equal
5
 *
6
 * [Observation]
7
 * Since the value is from 1 ~ 6
8
 *
9
 * Min sum of the array = len(arr)
10
 * Max sum of the array = 6 len(arr)
11
 *
12
 * When to arrays range cannot overlap -> no answer
13
 *
14
 * If there is a answer -> sum s, value will be between s1 and s2
15
 * So, let's say if s1 is smaller, we would like to increase s1's element and
16
 * decrease s2's element
17
 * -> We only have to design for s1 is smaller than s2.
18
 *
19
 * [Key] Which element's should we increase and decrease?
20
 * To minimize the changing elements, we change the number who can mostly
21
 * decrease the differences. So, we compare the smallest element in num1 and
22
 * largest in num2.
23
 * -> sorting
24
 *
25
 * @algo sorting + greedy
26
 * Time O(NlogN) for sorting
27
 * Space O(1)
28
 */
29
class Solution {
30
 public:
31
  int minOperations(vector<int> &nums1, vector<int> &nums2) {
32
    int l1 = nums1.size(); // l1 ~ 6l1
33
    int l2 = nums2.size(); // l2 ~ 6l2
34

35
    if (6 * l1 < l2 || 6 * l2 < l1) {
36
      return -1;
37
    }
38

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

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

49
    while (diff > 0) {
50
      if (ptr2 == l2 || ptr1 < l1 && (6 - nums1[ptr1]) >= (nums2[ptr2] - 1)) {
51
        diff -= (6 - nums1[ptr1]);
52
        ans++;
53
        ptr1++;
54
      } else {
55
        diff -= (nums2[ptr2] - 1);
56
        ans++;
57
        ptr2++;
58
      }
59
    }
60
    return ans;
61
  }
62
};