Equalize List Sums with Minimal Updates - Amazon Top Interview Questions

                        Solution in C++ :

int solve(vector<int>& A, vector<int>& B) {
    if (max(A.size(), B.size()) > 6 * min(A.size(), B.size())) return -1;
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    int sum1 = 0, sum2 = 0;

    for (int i : A) sum1 += i;
    for (int i : B) sum2 += i;

    if (sum1 > sum2) return solve(B, A);

    // sum1 is always smaller
    reverse(B.begin(), B.end());
    int i = 0, j = 0;
    int res = 0;

    int dif = sum2 - sum1;
    while (dif > 0) {
        res++;
        if (i < A.size() && j < B.size()) {
            int a = 6 - A[i];
            int b = B[j] - 1;
            if (a > b) {
                dif -= a;
                i++;
            } else {
                dif -= b;
                j++;
            }
        } else {
            if (i < A.size()) {
                dif -= (6 - A[i++]);
            } else if (j < B.size()) {
                dif -= (B[j++] - 1);
            }
        }
    }
    return res;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int[] A, int[] B) {
        int[] ops = new int[10]; // number of operations of each change value
        int diff = Math.abs(sum(A) - sum(B));
        if (sum(A) > sum(B)) {
            for (int a : A) ops[a - 1] += 1;
            for (int b : B) ops[6 - b] += 1;
        } else {
            for (int a : A) ops[6 - a] += 1;
            for (int b : B) ops[b - 1] += 1;
        }
        int ans = 0;
        int ind = 9;
        // greedily pick the operation which causes the biggest change
        while (ind > 0) {
            while (ind > 0 && ops[ind] == 0) ind--;
            if (diff <= 0)
                break;
            ans++;
            diff -= ind;
            ops[ind] -= 1;
        }
        if (diff <= 0) {
            return ans;
        } else {
            return -1;
        }
    }

    public int sum(int[] A) {
        int s = 0;
        for (int a : A) s += a;
        return s;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, a, b):
        if max(len(a), len(b)) > 6 * min(len(a), len(b)):
            return -1

        sum_a = sum(a)
        sum_b = sum(b)
        if sum_a > sum_b:
            a, b = b, a
            sum_a, sum_b = sum_b, sum_a

        counts = [0] * 6
        for x in a:
            counts[6 - x] += 1
        for x in b:
            counts[x - 1] += 1

        diff = sum_b - sum_a
        updates = 0
        for x in range(5, 0, -1):
            used = min(counts[x], ceil(diff / x))
            updates += used
            diff -= used * x
            if diff <= 0:
                break

        return updates