## Tuesday, 18 July 2017

### Algorithms | Find a pair of elements swapping which makes sum of two arrays same

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.
Examples:
Input: A[] = {4, 1, 2, 1, 1, 2}
B[] = (3, 6, 3, 3)
Output: {1, 3}

Sum of elements in array A = 11
Sum of elements in array B = 15
To get same sum from both arrays, we can swap 1 from array A and 3 from array B.

Input: A[] = {5, 7, 4, 6}
B[] = {1, 2, 3, 8}
Output: 6 2

package com.algorithm.forum;
import java.util.HashSet;
import java.util.Set;

public class FindSwapValues {

/**
* This is the naive approach will take O(n*m) time.
*/
private static void findSwapValuesNaive(int[] arrayA, int[] arrayB) {
int sumA = getSum(arrayA);
int sumB = getSum(arrayB);

outer:
for (int i = 0; i < arrayA.length; i++) {
int tempSumA = sumA - arrayA[i];
int tempSumB = sumB + arrayA[i];
for (int j = 0; j < arrayB.length; j++) {
if(tempSumA + arrayB[j] == tempSumB - arrayB[j]) {
System.out.println("Pair is : {"+ arrayA[i]+", "+ arrayB[j]+"}");
break outer;
}
}
}
}

/**
* Time complexity: O(n+m) and Space Complexity: O(n) as auxiliary space required.
* sumA - a + b = sumB+ a - b
* 2*a - 2*b = sumA - sumB.
* a - b = (sumA - sumB)/2.
* a = b + (sumA - sumB)/2.
* a = b + sumA_B2 where sumA_B2 = (sumA - sumB)/2.
*/
private static void findSwapValuesHash(int[] arrayA, int[] arrayB) {

System.err.println("Pair using Hash Set approach are: ");
int sumA = getSum(arrayA);
int sumB = getSum(arrayB);

int sumA_B2 = (sumA - sumB)/2;

Set<Integer> setA_s = new HashSet<Integer>();

for (int iValue : arrayA) {
}

for (int bValue : arrayB) {
int aValue = bValue + sumA_B2;

if(setA_s.contains(aValue)) {
System.out.println("Pair is : {"+ aValue+", "+ bValue+"}");
break;
}
}
}

/** Utility Method to get the sum. */
private static int getSum(int[] array) {
int sum = 0;
for (int value : array) {
sum += value;
}
return sum;
}

/** Driver method. */
public static void main(String[] args) {

int[] a = {4, 1, 2, 1, 1, 2};
int[] b = {3, 6, 3, 3};

findSwapValuesNaive(a,b);

findSwapValuesHash(a,b);
}
}