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);
      }

}


No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...