[Solved] find two element a and b from set A and B such that on swapping these elements, sum of sets is equal

by


Put the elements of set A into a structure that allows to test set membership in O(1) (for example a hash table or a bit vector if the range of elements is small). This will run in O(n).

Now iterate through the set B and check if there is an element in A that is the correct distance (half the difference of the sums) away from the element in B. This will also run in O(n).

Here is some pseudo code, where the set A is represented in such a way that the contains operation runs in O(1):

sumA = sum(A);
sumB = sum(B);
foreach (b in B) {
    a = b + (sumA - sumB)/2;
    if (A contains a) {
        return pair(a, b);
    }
}
return "no solution";

0

solved find two element a and b from set A and B such that on swapping these elements, sum of sets is equal