Find Triplet Whose Sum is Equal to Given Number

  • Write a program to find three elements of given array whose sum is equal to K
  • Algorithm to find a triplet whose sum is equal to given number.

Given an integer array of size N and an integer K. We have to find three array elements whose sum is equal to K.
For Example :

Input Array : 23, 8, 7, 7, 1, 9, 10, 4, 1, 3
K = 17
Output : 7, 7, 3

Let inputArray be an integer array of size N and we want to find a triplet whose sum is K.

Brute Force Approach
  • Using three for loops, generate all possible combinations of triplets and compare their sum with K. If sum of triplet is equal to K then print otherwise continue.
Time Complexity : O(n3)

C program to find triplet whose sum is given number

#include<stdio.h>
 
int isTripletSum(int *array, int size, int K) {
    int i, j, k;
 
    /* Brute Force Approach : Check the sum of all 
 possibel combinations of triplets */
    for(i = 0; i < size-2; i++) {
       for (j = i+1; j < size-1; j++) {
           for (k = j+1; k < size; k++) {
           /* Check if the sum of current triplets
           is equal to "K" */
               if(array[i] + array[j] + array[k] == K) {
                 printf("Triplet Found : %d, %d, %d", array[i], array[j], array[k]);
                 return 1;
               }
           }
       }
    }
    /* No triplet found whose sum is equal to K */
    return 0;
}
  
int main() {
    int array[10] = {23, 8, 7, 7, 1, 9, 10, 4, 1, 3};
    /* find a triplet whose sum is 17 */
    if(!isTripletSum(array, 10, 17)){
     printf("No Triplet Found");
    }    
 
    return 0;
}
Output
Triplet Found : 7, 7, 3
By Sorting Input Array
Let firstIndex, secondIndex and thirdIndex are three integer variables.
  • Sort inputArray using any O(nLogn) average time sorting algorithm like quick sort or merge sort.
  • Initialize firstIndex to 0. Using firstIndex traverse inputArray from index 0 to N-2 and fix first element of triplet.
  • Now, we have to find two array elements whose sum is equal to K-inputArray[firstIndex]. Let S = K-inputArray[firstIndex]
    • Initialize secondIndex and thirdIndex to firstIndex+1 and N-1.(secondIndex=firstIndex+1; thirdIndex=N-1)
    • If the sum of second and third element is equal to S, then we found one triplet.
    • If the sum of second and third element is less than S, increment seconIndex else decrement third index.
    • Continue until secondIndex < thirdIndex.
Time Complexity : O(n2) 
#include <stdio.h>

/* Swap array element at index left and right */
void swap(int array[], int left, int right) {
    int temp;
    /* Swapping using a temp variable */
    temp = array[left];
    array[left]=array[right];
    array[right]=temp; 
}
 
void quickSort(int array[], int left, int right) {
    int pivot; 
    if (right > left) {
        /* Partition the given array into 
        two segment by calling partion function */
        pivot = partition(array, left, right);
     
        /* Recursively sort left and right sub array*/
        quickSort(array, left, pivot-1);
        quickSort(array, pivot+1, right);
    }
}
 
int partition(int array[], int left, int right) {
    int temp = left;
    int pivot = array[left];
    
    while(left < right) {
        /* From left side, search for a number
  greater than pivot element */ 
        while(array[left] <= pivot) 
            left++;
        /* From right side, search for a number 
  less than pivot element */ 
        while(array[right] > pivot) 
            right--;
    
        /*Swap array[left] and array[right] */
        if(left < right) 
            swap(array, left, right);
    }
   /* Put pivot element in it's currect position '*/ 
   array[temp] = array[right];
   array[right] = pivot;
   /* Return partition index. All elements left of 
   right index is < pivot whereas elements right 
   side of right index are > pivot element */ 
   return right;
}

/*
This function prints triplet whose sum is equal to K
*/
int isTripletSum(int *array, int size, int K) {
    int first, second, third, currentSum, sum;

    /* Sort elements of array using quick sort algorithm  */
    quickSort(array, 0, size-1);
    
    /* Fix first element */
    for(first = 0; first < size-2; first++) {
      /* Initialize second and third to next element of first and 
   last index of array respectively */
      second = first+1;
      third = size-1; 
      /* sum id the remianing value of K to be found */
      sum = K - array[first];
      while(second < third) {
         currentSum = array[second] + array[third];
          /*Check if sun of array[second] and array[third] 
   is equal to sum */
          if(currentSum == sum) {
             printf("Triplet found : %d, %d, %d\n", array[first], 
       array[second], array[third]);
             return 1;
          } else if(currentSum < sum) {
              /* If currentSum < sum, then increase the value 
               of currentSum by incrementing left index */
              second++;
          } else {
              /* currentSum is greater than sum, decrease 
              value of currentsum by decrementing right index */
              third--; 
   } 
      }    
    }
    return 0;
}

int main(){
    int array[10] = {23, 8, 7, 7, 1, 9, 10, 4, 1, 3};
    /* find a triplet whose sum is 17 */
    if(!isTripletSum(array, 10, 17)){
     printf("No Triplet Found");
    }    
 
    return 0;
}
Output
Triplet found : 1, 7, 9
Using Hash Table
Algorithm to find three numbers whose sum is equal to K using hash table.
  • Traverse inputArray and put each element in hash table.
  • Using two for loops, generate all possible combinations of two elements and find their sum. Let S = inputArray[i] + inputArray[j].
  • Check if (K-S) exists in hash table. If true then we found a triplet (inputArray[i], inputArray[j] and K-S) whose sum is K.
Time Complexity : O(n2)
Posted by
Labels: ,