Find Triplet in Array With a Given Sum

Difficulty Level Medium
Frequently asked in Accolite Adobe Amazon Apple Bloomberg ByteDance Cisco Citadel Citrix DoorDash eBay Facebook Goldman Sachs Google Hulu IBM Infosys Mathworks Microsoft Morgan Stanley Oracle PayPal Qualtrics Samsung ServiceNow Splunk Square Tencent Tesla Uber Visa VMware Walmart Labs Yahoo Zoho
Akamai Array CarWale Groupon Postmates Works ApplicationsViews 4651

Problem Statement

Given an array of integers, find the combination of three elements in the array whose sum is equal to a given value X. Here we will print the first combination that we get. If there is no such combination then print -1.

Example

Input

N=5, X=15

arr[] = {10, 4, 2, 3, 5}

Output 

10, 2, 3

Approach 1

Generating all the triplets and comparing the sum to the given value. The below algorithm contains three loops.

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, fix the second element as arr[j], where j ranges from  i+1 to N-1.
  4. After fixing the second element, fix the third element as arr[k], where k ranges from j+1 to N.
  5. Find the sum, arr[i] + arr[j] + arr[k].
  6. If the Triplet sum is equal to the value X, print the three elements else print -1.

Implementation

C++ Program for Find Triplet in Array With a Given Sum

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N,X;//size of the array
    cin>>N>>X;
    int arr[N];
    for(int i=0;i<N;i++)
    {
        cin>>arr[i];
    }
    for(int i=0;i<N;i++)
    {
        for(int j=i+1;j<N;j++)
        {
            for(int k=j+1;k<N;k++)
            {
                if( arr[i] + arr[j] + arr[k] == X)
                {
                   cout << arr[i] <<"  "<<arr[j]<<"  "<<arr[k];
                   return 1;
                }
            }
        }
    }
    cout<<-1<<endl;
    return 0;
}

Java Program for Find Triplet in Array With a Given Sum

import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int x = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int temp=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                for(int k=j+1;k<n;k++)
                {
                    if( a[i] + a[j] + a[k] == x)
                    {
                       System.out.println(a[i]+"  "+a[j]+"  "+a[k]);
                       i=n;j=n;k=n;
                       temp=1;
                    }
                }
            }
        }
        if(temp==0)
        System.out.println(-1);
    }
}
5 15
10 4 2 3 5
10  2  3

Complexity Analysis

Time Complexity

O(n*n*n) where n is the number of elements present in the array. Here we Ron three for loop and check for every possible triplet.

Space Complexity

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

Approach 2

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 a 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.

Implementation

C++ Program for Find Triplet in Array With a Given Sum

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N,X;//size of the array
    cin>>N>>X;
    int arr[N];
    for(int i=0;i<N;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+N); //sort the array in ascending order
    int computed_sum;//sum computed at each step
  
    for(int i = 0; i < N - 2; i++) // fix one element and search for other two elements in linear time
    {
      int j = i+1 , k = N-1; // jth index starts from the next element of selected and k always starts at the ending index
      
      while(j < k)
      {
        computed_sum = arr[i] + arr[j] + arr[k]; // add the elements at the given indices
        
        if(computed_sum == X)
          {
            cout << arr[i] <<"  "<<arr[j]<<"  "<<arr[k];
            return 1;
          }
        else if(computed_sum < X) // means we need to increase some element but as i is fixed and k is already higher than i and j. We increment jth index
          j++;
          
        else if(computed_sum > X)//means we need to decrease some element but as i is fixed and j is already smaller than kth index element , we decrement k
          k--;
      }
    }
  cout<<-1<<endl;
    return 0;
}

Java Program for Find Triplet in Array With a Given Sum

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int x = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        Arrays.sort(a); //sort the array in ascending order
        int computed_sum;//sum computed at each step
        int temp=0;
        for(int i = 0; i < n - 2; i++) // fix one element and search for other two elements in linear time
        {
          int j = i+1 , k = n-1; // jth index starts from the next element of selected and k always starts at the ending index
          while(j < k)
          {
            computed_sum = a[i] + a[j] + a[k]; // add the elements at the given indices
            if(computed_sum == x)
              {
                System.out.println(a[i]+"  "+a[j]+"  "+a[k]);
                j=k;
                temp=1;
              }
            else if(computed_sum < x) // means we need to increase some element but as i is fixed and k is already higher than i and j. We increment jth index
              j++;
            else if(computed_sum > x)//means we need to decrease some element but as i is fixed and j is already smaller than kth index element , we decrement k
              k--;
          }
        }
        if(temp==0)
        System.out.println(-1);
    }
}
5 15
1 4 2 3 5
-1

Complexity Analysis

Time Complexity

O(n*n*n) where n is the number of elements present in the array. Here we Ron three for loop and check for every possible triplet.

Space Complexity

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

References

Translate »