## Wednesday, 3 May 2017

### Find a triplet that sum equals to X

If there is a triplet in an array whose sum is equal to the given value then print the triplet and return true otherwise return false.

Example: if the given array is {11, 4, 5, 2, 7, 10} and given sum is 21, then there is a triplet (4, 7 and 10) present in the array whose sum is 21.

Approach# 1 (Naive)
A simple method is to generate all possible triplets and compare the sum of every triplet with the given value.
Time Complexity: O(n^3)

public class TripletSumNaive {

/**
* Returns true if there is triplet with sum equal to 'value' present in A[]. Also, prints the triplet
* @param array
* @param value
* @return true/false
*/
private static boolean getTriplet(int[] array, int value) {
// Fix the first element as A[i]
for (int i = 0; i < array.length-2; i++) {
// Fix the second element as A[j]
for (int j = i+1; j < array.length-1; j++) {
// Now look for the third number
for (int k = j+1; k < array.length; k++) {
if(array[i]+array[j]+array[k]==value) {
System.out.println("Triplet is "+array[i]+", "+array[j]+", "+array[k]);
return true;
}
}
}
}
return false;
}

public static void main(String[] args) {
int value = 21;
int[] array = {11, 4, 5, 2, 7, 10};

boolean isExists = getTriplet(array,value);

System.out.println("Triplet exist: "+isExists);
}

}

Approach#2 (Sorting)
The time complexity of the Naive is O(n^3) and It can be reduced to O(n^2) by sorting the array first, and then using method 1 of this post in a loop.
1) Sort the input array.
2) Fix the first and last elements and keep traverse for the third element between first and last element.

import java.util.Arrays;

public class TripletSumNaive {

/**
* Returns true if there is triplet with sum equal to 'value' present in A[]. Also, prints the triplet
* @param array
* @param value
* @return true/false
*/
private static boolean getTriplet(int[] array, int value) {
Arrays.sort(array);

int left = 0;
int right = array.length-1;
while(left<right) {
int k = left + 1;

while(k<right) {
int sum = array[left]+array[right]+array[k];
if(sum==value) {
System.out.println("Triplet is "+array[left]+", "+array[k]+", "+array[right]);
return true;
} else if(sum>value) {
right--;
break;
} else if(sum<value && k<right-1) {
k++;
} else {
left++;
break;
}
}
}

return false;
}

public static void main(String[] args) {
int value = 21;
int[] array = {11, 4, 5, 2, 7, 10};

boolean isExists = getTriplet(array,value);

System.out.println("Triplet exist: "+isExists);
}

}