Table of Contents
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
- First sort the input array
- Fix the first element as arr[i], where i ranges from 0 to N-2.
- After Fixing the first element, fix the second element as arr[j], where j ranges from i+1 to N-1.
- After fixing the second element, fix the third element as arr[k], where k ranges from j+1 to N.
- Find the sum, arr[i] + arr[j] + arr[k].
- 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
- First sort the input array
- Fix the first element as arr[i], where i ranges from 0 to N-2.
- 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.
- 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.