Home » Technical Interview Questions » Array Interview Questions » Find a Triplet That Sum to a Given Value

Find a Triplet That Sum to a Given Value


Reading Time - 2 mins

In find a triplet that sum to a given value problem we have given an array of integers (positive and negative numbers) and you have to find a triplet (3 elements) in array whose sum is equal to the given value X.

Input Format

First-line containing two integer values N and X.

Second-line containing N integer values or input array.

Output Format

Print any triplet whose sum given to X. If there are more than one triplets found print any one of them. If no such triplet found print 0.

Constraints

  • 1<=N<=100000
  • -1e9<=a[i]<=1e9
  • -1e9<=X<= 1e9

Examples

Input

6, 10

1, 5, 7, 3, 4, 2
Output

1 7 2

Input

8, 11

-1, 12, 5, 7, -2, -4, 5, 1
Output

-2 1 12

Input

8, 0

-1, 12, 5, 7, -2, -4, 5, 1
Output

-4 -1 5

Approach Using 3 Pointers for Find a Triplet That Sum to a Given Value

    1. Sort the given array first which will give us time complexity of (n log n)
    2. Take 3 pointers p1, p2, p3 where p1 is pointing to start of the array, p2 will be pointing next to p1 and p3 will be pointing to the last index of an array.
      Find a Triplet That Sum to a Given Value
    3. Have a loop1 to move (Increment) p1 till p1 < p3
    4. For each iteration of loop1 have loop2 to move (Increment) p2 till p2 < p3
    5. If sum of Array[p1] + Array[p2] + Array[p3] > k then Decrement p3
    6. If sum of Array[p1] + Array[p2] + Array[p3] == k then Print the elements
    7. p2 = p1 +1 and p3 = Array.length – 1
READ  Length of Longest Fibonacci Subsequence

 C++ Program for Find a Triplet That Sum to a Given Value

#include <bits/stdc++.h>
using namespace std;
void findTriplets(int arr[], int n, int k)
 {
      sort(arr,arr+n);
      int p1=0, p2, p3, counter=0;
      p2 = p1 + 1;
      p3 = n-1;
    while(p1<p3)
    {
       while(p2<p3) 
       { 
          if((arr[p1] + arr[p2] + arr[p3]) > k)
          p3--;
          if(((arr[p1] + arr[p2] + arr[p3]) == k)&&(p2<p3)) 
          {
              cout<<arr[p1]<<" "<<arr[p2]<<" "<<arr[p3]<<endl;
              counter++; 
              goto label;
          } 
          p2++; 
       } 
       p1++; 
       p2=p1+1; 
       p3=n-1; 
    } 
    if(counter==0) 
    cout<<0<<endl;
    label:; 
} 
int main()
{
    int n,x;
    cin>>n>>x;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    findTriplets(a,n,x);
    return 0;
}
6 10
1 5 7 3 4 2
1 2 7

Complexity Analysis for Find a Triplet That Sum to a Given Value

Time Complexity

O(n*n*n) where n is the length of the array. Here we use 3 pointer method to traverse in the array. In the worst case the loop will run N*N*N times.

Space Complexity

O(1) because here we don’t use any auxiliary space here.

Approach 2 for Find a Triplet That Sum to a Given Value

Here also we need to find the triplets from an array whose sum is equal to the given number.

Algorithm

1. First sort the input array
2. Fix the first element as arr[i], where i ranges from 0 to N-2

3. After fixing the first element, for finding the next two elements, take two pointer like variables ( j = i+1, k= N-1) and traverse the algorithm for finding the sum in sorted array.

4. while j is less than k Add the elements at the given indexes ie, arr[i] + arr[j] + arr[k] if Triplet sum is equal to the value X, print the three elements else if Triplet sum is less than the value X, then increase the j value else decrease the value of k.

Find a Triplet That Sum to a Given Value

C++ Program for Find a Triplet That Sum to a Given Value

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,x;
    cin>>n>>x;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int flag=0;
    sort(a,a+n);//sort the array in ascending order
    int computed_sum;//sum computed at each step
    //fix one element and search for other two elements in linear time
    for(int i = 0; i <n-2; i++) 
    {
      //jth index starts from the next element of selected and k always starts at the ending index
      int j = i+1,k=n-1; 
      while(j<k)
      {
         //add the elements at the given indices 
         computed_sum=a[i]+a[j]+a[k]; 
         if(computed_sum==x)
         {
            cout<<a[i]<<" "<<a[j]<<" "<<a[k];
            return 1;
         }
         else if(computed_sum<x)
         {
            k--;
         }
         else
         {
            j++;
         }
      }
    }
    cout<<0<<endl;
  return 0;
}
8 0
-1 12 5 7 -2 -4 5 1
-4 -1 5

Complexity Analysis

Time Complexity

O(N2) where N is the size of the array. Here we fix I and then use two pointer methods for j and k values. This will take N*N time in the worst case.

READ  Sort an array according to the order defined by another array

Space Complexity

O(1) because we don’t use any auxiliary space.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions