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

Question

Set A = [2, 10, 5, 9] = sum[A] 26

Set B = [1, 10, 4, 9] = sum[B] 24

Find two elements a, b from set A and B such that

sum[A] - a + b = sum [B] - b + a

I solved this problem in O(n^2).

for(int i=0;i<4;i++){
    for(int j=0;j<4;j++){
        if(sumOfA - A[i] + B[j] == sumOfB + A[i] - B[j]){
            System.out.println("solution: " + A[i] + ", " + B[j])
            return;
        }
    }
}

How it can be improved to O(n)?

Answer 1

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";