Triplet Sum in Array | Amazon | Samsung
Question
Write a program to find triplet sum in array. Given an array A[] of N numbers and another number x, determine whether or not there exist three elements in A[] whose sum is exactly x.
Logic
- Get the array numbers and x from the user.
- Use nested for loop to generate each combination with three elements.
- If the sum of three elements equals the given x then Print the combination.
- If the exact combination is not found then print ‘not found’
Algorithm
- We create three for loop because we find triplet sum.
- From first for loop we get arr[i]. We keep this constant and change j and k.
- From second for loop we get arr[j]. We keep this constant and change k.
- We check sum by adding arr[i], arr[j], arr[k].
Program
include<iostream> using namespace std; int main() { int x = 10; int i,j,sum,n,k; int arr[20]; bool flag = true; cin>>x>>n; //get n numbers for(i=0; i<n; i++) { cin>>arr[i]; } /*Let the array= {1,2,4,3,6}*/ for(i=0; i<n-2; i++) //loop till n-2 items { /*EX: In first iteration we arr[0]=1 in first iteration once all the possibilities for combination starting with 1 complete, we increment*/ for(j=i+1; j<n-1&&flag; j++) //loop till n-1 items { /*EX: In first iteration of this loop we check arr[1]=2 with other combinations so 1+2+arr[k]*/ for(k=j+1; k<n&&flag; k++) { sum=arr[i]+arr[j]+arr[k]; /*If sum equals given number*/ if(sum==x) { cout<<arr[i]<<"+"<<arr[j]"+"<<arr[k]<<"="<<sum; flag = false; break; } } } } /*If triplet not found*/ if(flag) { cout<<"not found"; } return 0; }