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) {
                setA_s.add(iValue);
           }
          
           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);
     }
}

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...