Given two arrays of integers, we want to find all pairs of 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 sum at the end.
Example:
int[] a = { 1,5,2,3,4,7 };
int[] b = { 2,1,5,10};
answer: {3,1}, {4,2}, {7,5} 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).
Also {7,5} can be the answer. It means if you switch 7 and 5 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 List<IList<int>> FindTwoElements(int[] A, int[] B) {
IList<IList<int>> res = new List<List<int>>();
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)) {
List<int> pair = new List<int>();
pair.Add(a);
pair.Add(a-target);
res.Add(pair);
}
}
return res;
}