Given two arrays of integers, find a pair of values (one value from each array) that you can swap to give the two arrays the same sum.
We are looking for two values, a and b, such that:
sumA - a + b = sumB - b + a
Doing some quick math:
2a - 2b = sumA - sumB
a - b = (sumA - sumB) / 2
Therefore, we're looking for two values that have a specific target difference: (sumA - sumB) / 2. The difference between the sums must be even to have a valid pair.
X.
int[] findSwapValues(int[] arrayl, int[] array2) {
Integer target= getTarget(arrayl, array2);
if (target== null) return null;
return findDifference(arrayl, array2, target);
}
/* Find a pair of values with a specific difference.*/
int[] findDifference(int[] arrayl, int[] array2, int target) {
HashSet<Integer> contents2 = getContents(array2);
for (int one : arrayl) {
int two= one - target;
if (contents2.contains(two)) {
int[] values = {one, two};
return values;
}
}
return null;
}
/* Put contents of array into hash set. */
HashSet<Integer> getContents(int[] array) {
HashSet<Integer> set= new HashSet<Integer>();
for (int a : array) {
set.add(a);
}
return set;
}
If the arrays are sorted, we can iterate through them to find an appropriate pair. This will require less space.
https://github.com/careercup/CtCI-6th-Edition/blob/39a4e384757c3716faba4492b7530f752669e812/Java/Ch%2016.%20Moderate/Q16_21_Sum_Swap/QuestionD.java
https://github.com/careercup/CtCI-6th-Edition/blob/39a4e384757c3716faba4492b7530f752669e812/Java/Ch%2016.%20Moderate/Q16_21_Sum_Swap/QuestionD.java
int[] findSwapValues(int[] arrayl, int[] array2) {
Integer target = getTarget(arrayl, array2);
if (target == null) return null;
return findDifference(arrayl, array2, target);
}
int[] findDifference(int[] arrayl, int[] array2, int target) {
int a = 0;
int b = 0;
while (a < arrayl.length && b < array2.length) {
int difference = arrayl[a] - array2[b];
/* Compare difference to target. If difference is too small, then make it
* bigger by moving a to a bigger value. If it is too big, then make it
* smaller by moving b to a bigger value. If it's just right, return this
* pair. */
if (difference == target) {
int[] values = {arrayl[a], array2[b]};
return values;
} else if (difference < target) {
a++;
} else {
b++;
}
}
return null;
}
int[] findSwapValues(int[] arrayl, int[] array2) {
Integer target = getTarget(arrayl, array2);
if (target== null) return null;
for (int one : arrayl) {
for (int two : array2) {
if (one - two== target) {
int[] values= {one, two};
return values;
}
}
}
return null;
}
Integer getTarget(int[] arrayl, int[] array2) {
int suml = sum(arrayl);
int sum2 = sum(array2);
if ((suml - sum2) % 2 != 0) return null;
return (suml - sum2) / 2;
}
https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2016.%20Moderate/Q16_21_Sum_Swap/QuestionB.java
public static int[] findSwapValues(int[] array1, int[] array2) {
int sum1 = sum(array1);
int sum2 = sum(array2);
for (int one : array1) {
for (int two : array2) {
int newSum1 = sum1 - one + two;
int newSum2 = sum2 - two + one;
if (newSum1 == newSum2) {
int[] values = {one, two};
return values;
}
}
}
return null;
}
https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2016.%20Moderate/Q16_21_Sum_Swap/QuestionA.java
https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2016.%20Moderate/Q16_21_Sum_Swap/QuestionB.java
public static int[] findSwapValues(int[] array1, int[] array2) {
int sum1 = sum(array1);
int sum2 = sum(array2);
for (int one : array1) {
for (int two : array2) {
int newSum1 = sum1 - one + two;
int newSum2 = sum2 - two + one;
if (newSum1 == newSum2) {
int[] values = {one, two};
return values;
}
}
}
return null;
}
https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2016.%20Moderate/Q16_21_Sum_Swap/QuestionA.java
int[] findSwapValues(int[] arrayl, int[] array2) {
int suml sum(arrayl);
int sum2 = sum(array2);
for (int one : arrayl) {
for (int two : array2) {
int newsuml = suml - one + two;
int newSum2 = sum2 - two + one;
if (newsuml == new5um2) {
int [] values = { one, two};
}
}
return values;
}
return null;
}
