Home » Interview Questions » Array Interview Questions » Find triplet in array with a given sum

Find triplet in array with a given sum


()

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.

For example

Input :

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

Output : 

10, 2, 3

Algorithm 1

Time complexity : O(n^3)

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

1. First sort the input array
2. Fix the first element as arr[i], where i ranges from 0 to N-2
a. After Fixing the first element, fix the second element as arr[j], where j is ranges from  i+1 to N-1
b. 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

C++ Program

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int arr[] = {18, 17, 8, 10, 19, 11, 12, 3, 4, 1, 6, 9}; //array
	int N = sizeof(arr)/sizeof(arr[0]);//size of array
	
	
	int X;
	cin>> X; //number to which a triplet should sum to
	
	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<<"No Such triplet exists\n";
	return 0;
}

Algorithm 2

Time Complexity: O(N^2)

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

READ  Last Stone Weight

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

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

C++ Program

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int arr[] = {18, 17, 8, 10, 19, 11, 12, 3, 4, 1, 6, 9}; //array
	int N = sizeof(arr)/sizeof(arr[0]);//size of array
	
	
	int X;
	cin>> X; //number to which a triplet should sum to
	
	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<<"No Such triplet exists\n";
	return 0;
}

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

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