Swap the elements of two sequences, such that the difference of the element-sums gets minimal.

Question

An interview question:

Given two non-ordered integer sequences a and b, their size is n, all numbers are randomly chosen: Exchange the elements of a and b, such that the sum of the elements of a minus the sum of the elements of b is minimal.

Given the example:

a = [ 5 1 3 ]
b = [ 2 4 9 ]

The result is (1 + 2 + 3) - (4 + 5 + 9) = -12.

My algorithm: Sort them together and then put the first smallest n ints in a and left in b. It is O(n lg n) in time and O(n) in space. I do not know how to improve it to an algorithm with O(n) in time and O(1) in space. O(1) means that we do not need more extra space except seq 1 and 2 themselves.

Any ideas ?

An alternative question would be: What if we need to minimize the absolute value of the differences (minimize |sum(a) - sum(b)|)?

A python or C++ thinking is preferred.

Answer 1

Revised solution:

1. Merge both lists x = merge(a,b).

2. Calculate median of x (complexity O(n) See http://en.wikipedia.org/wiki/Selection_algorithm )

3. Using this median swap elements between a and b. That is, find an element in a that is less than median, find one in b that is more than median and swap them

Final complexity: O(n)

Minimizing absolute difference is NP complete since it is equivalent to the knapsack problem.

Answer 2

What comes into my mind is following algorithm outline:

1. C = A v B
2. Partitially sort #A (number of A) Elements of C
3. Subtract the sum of the last #B Elements from C from the sum of the first #A Elements from C.

You should notice, that you don't need to sort all elements, it is enough to find the number of A smallest elements. Your example given:

1. C = {5, 1, 3, 2, 4, 9}
2. C = {1, 2, 3, 5, 4, 9}
3. (1 + 2 + 3) - (5 + 4 + 9) = -12

A C++ solution:

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    // Initialize 'a' and 'b'
    int ai[] = { 5, 1, 3 };
    int bi[] = { 2, 4, 9 };
    std::vector<int> a(ai, ai + 3);
    std::vector<int> b(bi, bi + 3);

    // 'c' = 'a' merged with 'b'
    std::vector<int> c;
    c.insert(c.end(), a.begin(), a.end());
    c.insert(c.end(), b.begin(), b.end());

    // partitially sort #a elements of 'c'
    std::partial_sort(c.begin(), c.begin() + a.size(), c.end());

    // build the difference
    int result = 0;
    for (auto cit = c.begin(); cit != c.end(); ++cit)
        result += (cit < c.begin() + a.size()) ? (*cit) : -(*cit);

    // print result (and it's -12)
    std::cout << result << std::endl;
}