minimum time to change arrays to make sums of two arrays equal

Question

The input is two arrays, each one up to length 6 and each element in the array can be some number from [1, 2, 3, 4, 5, 6]. Return minimum number to change the arrays to make the sum of two arrays equal.

For example, A = [5, 4, 1, 2, 6, 5], B = [2]; return 6 because we can turn five dice in A to get [1, 1, 1, 1, 1, 1] and one dice in B to get [6]; then the arrays will have the same sums.

My first thought is to compute the sum of two arrays respectively: Sum(A) = 23, Sum(B) = 2.

Then the brute force way is compute required changes of making the sum equal to 2, 3, 4, ..., 23.

But I think the time complexity is too high.

The hard part of this problem is we do not know what the target sum we try to merge is.

Although in the given example, the minimum sum of A is 6, the max sum value of B is 6, so we know they will overlap at 6 so we can cut other branches.

Answer 1

A greedy algorithm should work well for this:

• determine which of the arrays has the larger sum and which the smaller
• optional: sort the arrays to make the following steps faster
• while the sum is not the same:
  • get the maximum element from the larger, and the minimum element from the smaller array
  • determine which has more "potential" to equalize the sum, e.g. a 5 in the "larger" array can be changed to 1, or a 3 in the smaller array can be changed to 6
  • pick the element that has more "potential" and change it (all the way to 1 or 6, or as needed)

The complexity without sorting is at most O(n²) for repeatedly finding the min and max elements, and can be reduced to O(n logn) by sorting the arrays once and then just iterating the elements in order. (You do not have to re-sort the arrays or recalculate the sums since you know which elements you changed by how much and you do not have to look at those again.)