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.

user_1639625 · Answer

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.)

user_10553341 · Answer

As you mentioned yourself with a tag, a simple solution is obtained by a greedy algorithm. Let us assume the sum of A is greater than the sum of B.

Then we have in priority to consider the modifications of the largest elements of A, and of the minimum elements of B. This can be performed by first sorting these two arrays (a max-heap and a min-heap could also be used).

Here is a code in C++. As it is very simple, I suppose you will understand it easily.

#include 
#include 
#include 
#include 

int n_changes (std::vector &A, std::vector &B) {
    int sum_A = std::accumulate (A.begin(), A.end(), 0);
    int sum_B = std::accumulate (B.begin(), B.end(), 0);
    
    if (sum_A == sum_B) return 0;
    if (sum_A < sum_B) {
      std::swap (A, B);
      std::swap (sum_A, sum_B);
    }
    
    std::sort (A.begin(), A.end(), std::greater());
    std::sort (B.begin(), B.end());
    int nA = A.size();
    int nB = B.size();
    
    int count = 0;
    int iA = 0;
    int iB = 0;
    int candidate_A, candidate_B;
    while (sum_A > sum_B) {
        if (iA < nA) candidate_A = A[iA]; else candidate_A = 1;
        if (iB < nB) candidate_B = B[iB]; else candidate_B = 6;
        if ((candidate_A == 1) && (candidate_B == 6))  break;
        count ++;
        if ((candidate_A -1) > (6 - candidate_B)) {
            iA++;
            sum_A += (1 - candidate_A);
        } else {
            iB++;
            sum_B += (6 - candidate_B);
        }
    }
    if (sum_A > sum_B) count = -1;
    return count;
}

int main() {
    std::vector A = {5, 4, 1, 2, 6, 5};
    std::vector B = {2};

    std::cout << n_changes (A, B) << "
";
}

user_15171945 · Answer

Think about the case where you can't solve at all
Don't sort the array, instead build 2 maps of size 6 each (that's O(N) to build and look up will be O(1)) + compute the sum
Then apply greedy algorithm on the difference to move by the maximum step etc. until the diff is zero (again O(N) complexity)

Overall complexity is O(N)

Python code:

    def _cast_to_dict(A):
        initial_dict = {i: 0 for i in range(1, 7)}
        total_sum = 0
        for a in A:
            total_sum += a
            initial_dict[a] += 1
        return initial_dict, total_sum      
    
    def solution(A, B):
        if len(A) > 6 * len(B) or len(B) > 6 * len(A):
             # Case where the problem is not solvable
            raise ValueError("Impossible to achieve")
        state_of_A, sum_A = _cast_to_dict(A)
        state_of_B, sum_B = _cast_to_dict(B)
    
        total_moves = 0
        if sum_A == sum_B:
            return 0
        elif sum_A < sum_B:
            state_of_A, state_of_B = state_of_B, state_of_A
            sum_A, sum_B = sum_B, sum_A
        # Now we can assume sum_A > sum_B
        # to reduce the diff, we can either increase B or decrease A
        diff = sum_A - sum_B
    
        print('DIFF %i' % diff)
        possible_jumps = {5: [(6, 1)], 4:[(6, 2), (5, 1)], 3:[(6, 3), (5, 2), (4, 1)], 2:[(6, 4), (5, 3), (4, 2), (3, 1)], 1:[(6, 5), (5, 4), (4, 3), (3, 2), (2, 1)]}
        while diff > 0:
            max_diff_to_jump = min(5, diff)
            for possible_jump in range(max_diff_to_jump, 0, -1):
                is_jump_realized = False
                print('Possible jump %i' % possible_jump)
                for swap in possible_jumps[possible_jump]:
                    if state_of_A[swap[0]] > 0:
                        print('flipping A with (%s, %s)' % swap)
                        state_of_A[swap[0]] -= 1
                        state_of_A[swap[1]] += 1
                        diff -= possible_jump
                        total_moves += 1
                        is_jump_realized = True
                        break
                    elif state_of_B[swap[1]] > 0:
                        print('flipping B with (%s, %s).T' % swap)
                        state_of_B[swap[1]] -= 1
                        state_of_B[swap[0]] += 1
                        diff -= possible_jump
                        total_moves += 1
                        is_jump_realized = True
                        break                  
                if is_jump_realized:
                        break
        return total_moves

user_13879234 · Answer

here is an illustration of the logic behind the code

def changes_to_equal_sums(a, b):
    # organize into dict so we can determine what list has the bigger sum
    sums = {
        sum(a): a,
        sum(b): b
    }
    # get the bigger sum list and sort it in descending order
    big_sum_dice = sorted(sums[max(sums.keys())], reverse=True)
    # get the smaller sum list and sort it in ascending order
    small_sum_dice = sorted(sums[min(sums.keys())])
    # calculate the delta/distance we need to equalize between the two sums
    dist = sum(big_sum_dice) - sum(small_sum_dice)
    # count the number of changes we have made
    count = 0
    # pointer to the last index in the big_sum_dice list
    last_big = 0
    # pointer to the last index in the small_sum_dice list
    last_small = 0

    # a while loop that will run when the sums aren't equal and while we didn't run out of index range (of both lists)
    while sum(big_sum_dice) != sum(small_sum_dice) and len(big_sum_dice)+len(small_sum_dice) > last_small+last_big:

        # choose more efficient element to change -
        # the most efficient elements to change are:
        # - from the big_sum_list, the numbers closer to 6
        # - from the small_sum_list, the numbers closer to 1
        if len(small_sum_dice) <= last_small or big_sum_dice[last_big] - 1 > 6 - small_sum_dice[last_small]:
            # check if the margin of the given number allows us to finally equalize the sums
            if dist < big_sum_dice[last_big]:
                count+=1
                big_sum_dice[last_big] = big_sum_dice[last_big] - dist
            # if not so we change the margin to the extreme - which is 1
            else:
                dist = dist - (big_sum_dice[last_big] -1)
                big_sum_dice[last_big] = 1
                count +=1
                last_big +=1
        else:
            # check if the margin of the given number allows us to finally equalize the sums
            if dist < 6-small_sum_dice[last_small]:
                count+=1
                small_sum_dice[last_small] = small_sum_dice[last_small] + dist
            # if not so we change the margin to the extreme - which is 6
            else:
                dist = dist - (6 - small_sum_dice[last_small])
                small_sum_dice[last_small] = 6
                count+=1
                last_small+=1

    # in case of no possible option (for ex. [1] [1,1,1,1,1,1,1]) return -1
    if sum(big_sum_dice) != sum(small_sum_dice):
        return -1
    return count


# for ex. :

A = [5, 4, 1, 2, 6, 5]
B = [2]
print(changes_to_equal_sums(A,B))

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

4 Answers