LeetCode 1775. Equal Sum Arrays With Minimum Number of Operations

Posted on Edited on In 
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
class Solution {
public:
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        const int l1 = nums1.size(), l2 = nums2.size();
        if (min(l1, l2) * 6 < max(l1, l2)) return -1;
        int s1 = accumulate(begin(nums1), end(nums1), 0), s2 = accumulate(begin(nums2), end(nums2), 0);
        if (s1 > s2) return minOperations(nums2, nums1);
        if (s1 == s2) return 0;
        sort(begin(nums1), end(nums1));
        sort(rbegin(nums2), rend(nums2));
        int ans = 0;
        for (int i = 0, j = 0; s1 < s2; ++ans) {
            int d1 = i == l1 ? 0 : 6 - nums1[i];
            int d2 = j == l2 ? 0 : nums2[j] - 1;
            if (d1 >= d2) {
                s1 += d1;
                ++i;
            } else {
                s2 -= d2;
                ++j;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        const int l1 = nums1.size(), l2 = nums2.size();
        if (l1 * 6 < l2 || l2 * 6 < l1) return -1;
        int s1 = accumulate(begin(nums1), end(nums1), 0), s2 = accumulate(begin(nums2), end(nums2), 0);
        if (s1 > s2) return minOperations(nums2, nums1);
        int cnt[6] = {0}, i = 5, ans = 0;
        for (int num : nums1) ++cnt[6 - num];
        for (int num : nums2) ++cnt[num - 1];
        while (s1 < s2) {
            while (cnt[i] == 0) --i;
            s1 += i;
            --cnt[i];
            ++ans;
        }
        return ans;
    }
};

Reference: [Java/Python 3] 2 Greedy codes: sort and count w/ brief explanation and analysis. - LeetCode Discuss