Given two arrays of integers, we want to find two integers one from each array in such a way that if we swap these two integers the sum of the elements of each array will be equal. We are trying to balance the disproportional arrays to have the same total at the end.
Example:
int[] a = { 4, 1, 2, 1, 1, 2 };
int[] b = { 3, 6, 3, 3 };
answer: {1,3}. It means if you switch 1 and 3 from both arrays the sum of the elements of the array will be equal (13).
Example:
int[] a = { 1,5,2,3,4,7 };
int[] b = { 2,1,5,10};
answer: {3,1}. It means if you switch 3 and 1 from both arrays the sum of the elements of the array will be equal (20).
Also {4,2} can be the answer. It means if you switch 4 and 2 from both arrays the sum of the elements of the array will be equal (20).
Solution
Strategy here is do the math.
Lets say s1 is the sum of all elements in array 1 (int [] A)
Lets say s2 is the sum of all elements in array 2 (int [] B)
Therefore we are trying to make s1 = s2 only on one condition and that is we swap two numbers (say a coming out of A and put it in to B and b coming out of B and put it in to A)
s1+ b - a = s2 + a - b
s1-s2 = 2a - 2b
s1 - s2 = 2(a-b)
(s1-s2)/2 = a-b
a = (s1-s2)/2 + b
Let target = (s1-s2)/2
Then a = target + b
b = a - target.
Now, throw all items of B in hashset (not hashtable because we don't want to store and retrieve by key. We just want to check the existence of a value in a set) then loop A and look for if any element in A, ai equals ai - target.
public static int[] FindTwoElements(int[] A, int[] B) {
int sum1 = 0, sum2 = 0;
foreach(int a in A)
sum1 += a;
foreach(int b in B)
sum2 +=b;
HashSet<int> ht = new HashSet<int>();
int target = Math.Abs(sum1 - sum2) / 2;
foreach(int b in B)
ht.Add(b);
foreach(int a in A) {
if(ht.Contains(a - target )) {
return new int[] { a, a - target };
}
}
return new int[] { };
}