Count The Triplets - Best Optimal Solution

Prashant | Thu, 04 Jun, 2020 | 708

Count the triplets - Best Optimal solution 

Counting the triplets is mostly asked in competitive programming, placements and interviews, as it can be done in many ways but you need to use the best optimal solution in order to impress HR or get pass in placements rounds.

Nothing to worry about, We are here to help you out.

Just follow the given procedure.

Question description

Given an array of distinct integers. The task is to count all the triplets such that sum of two elements equals the third element.

Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of two lines. First line of each test case contains an Integer N denoting size of array and the second line contains N space separated elements.

Output:
For each test case, print the count of all triplets, in new line. If no such triplets can form, print "-1".

Constraints:
1 <= T <= 100
3 <= N <= 105
1 <= A[i] <= 106

Example:
Input:

2
4
1 5 3 2
3
3 2 7
Output:
2
-1

Explanation:
Testcase 1:
 There are 2 triplets: 1 + 2 = 3 and 3 +2 = 5

Best optimal Solution  in CPP

#include<bits/stdc++.h>
using namespace std;
int main()
 {
	int t;
	cin>>t;
	while(t--){
	    int n,res=0;cin>>n;
	    int arr[n]; // we recomend to use vector.
	    for(int i=0;i<n;i++)cin>>arr[i];
	    sort(arr,arr+n); // sorting array
	    for(int i=n-1;i>=0;i--){
	        int a=arr[i],b=0,c=i-1,x;
	        while(b<c){
    	        if(b>=0 && c>=0){
    	            x=arr[b]+arr[c];
    	            if(x==a){
    	                res++;b++;c++;
    	            }
    	            else if(x<a)b++;
    	            else c--;
    	        }
	        }
	    }
	    if(res==0)cout<<"-1\n";
	    else
	    cout<<res<<endl;
	    
	}
	return 0;
}

Feel free to contact us if you feel any difficulty in understanding any topic.

0 comments
Leave a comment