Wednesday 5 August 2015

Find triplets where sum is equal to x

For a given array find a1, a2 and a3 such that a1+a2+a3  = x.

We can solve this problem by sorting the array, and apply following logic.

Fix one element in array (a1) and  scan the array using two pointers one from beginning and other from end of the array to find a2 and a3.

import java.util.*;

public class TripletSum {

 public List<String> getSum(int arr[], int sum){
  List<String> result = new ArrayList<> ();

  Arrays.sort(arr);
  
  for(int i=0; i<arr.length; i++){
   int a1 = arr[i];
   int remSum = sum-a1;
   
   int leftCounter = i+1, rightCounter=arr.length-1;
   
   while(leftCounter < rightCounter){
    if(arr[leftCounter] + arr[rightCounter] == remSum){
     result.add(a1 + "," + arr[leftCounter] + "," + arr[rightCounter]);
    }
    
    if(arr[leftCounter] + arr[rightCounter] < remSum)
     leftCounter++;
    else
     rightCounter--;
   }
  }
  
  return result;
 }
}

public class TripletSumTest {
 public static void main(String arg[]){
  TripletSum tripletSum = new TripletSum();
  
  System.out.println(tripletSum.getSum(new int[]{1, 4, 45, 6, 10, 8}, 22));
  System.out.println(tripletSum.getSum(new int[]{2, 4, 6, 8, 10, 12, 14}, 16));
 }
}


No comments:

Post a Comment