Last Updated: 28 Dec, 2020
Sum of Two Elements Equals the Third.
Easy
Asked in companies
You are given an array Arr consisting of n integers, you need to find a valid triplet as explained below.
An array is said to have a valid triplet {arr[i], arr[j], arr[k]} if there exists three indices i, j and k such that i != j, j != k and i != j and arr[i] + arr[j] = arr[k] or arr[i] + arr[k] = arr[j] or arr[k] + arr[j] = arr[i].
For Example:
Arr = 10, 5, 5, 6, 2,
In this array, the triplet {10, 5, 5} is valid triplet because, 5 + 5 = 10.
Note:
The elements in the array need not be distinct.
Input Format:
The first line of the input contains an integer T, denoting the number of test cases.
The first line of each test case contains the integer N, denoting the size of the array.
The second line of each test case contains N space-separated integers denoting the array elements.
Output Format:
For each test case, every line of output contains “true” if there is a valid triplet and the user has returned a valid one, else "false" will be printed.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N <= 10^3
1 <= Arr[i] <= 10^4
Time Limit: 1 sec
Approaches
- The most trivial approach would be to find any triplet in the array such that two of it’s elements sums up to the third element.
- We can find the answer using three nested loops for three different indexes and check if the values at those indexes can yield the required triplet.
- If for distinct indices we find the required triplet, return the answer list containing the three elements in it.
- If after iterating all the loops, no such triplet is found, return an empty list.
- Sort the array in non-decreasing order because after the array is sorted, we don’t have to process the same elements multiple times and hence we don’t have to explicitly keep track of distinct triplets. The other advantage of sorting the array is that if we have some value and we require a greater value, we know we have to look in only a single direction.
- Now since we want triplets such that x + y = z, we can fix z as arr[i]. So we want to find the sum of two numbers x and y as arr[i] in the array.
- Let us assume that we are the ith index of the array and initialise variable target to arr[i].
- So now we just need to find two elements x, y such that target = x + y.
- We will use two pointers, one will start from 0, and the other will start from i-1 as the ith index will traverse the sorted array from the largest elements towards the smallest element.
- Let the two pointers be j and k, where j=0 and k=i-1. Let sum = x + y, where x = arr[j] and y = arr[k]. We have to find the triplets such that target = sum.
- While j < k, there will be 3 cases:
- if(sum < target), we will have to increase the sum and hence increment the j pointer as we have sorted the array and to increase the sum, the greater element will always be present after the front index.
- Else if(sum > target), we will have to decrease the sum and hence decrease k pointer. The reason for this is exactly similar to the above point
- Else if(sum == target), we return the required triplets.
- If after iterating the entire sorted array we don’t find any such triplet, we return the empty list.