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);
}
}
No comments:
Post a Comment