Pythagorean Triplet

PROBLEM :
Given an array of integers, write a function that returns true if there is a triplet (a, b, c) that satisfies a2 + b2 = c2.

Input:
The first line contains 'T' denoting the number of testcases. Then follows description of testcases.
Each case begins with a single positive integer N denoting the size of array.
The second line contains the N space separated positive integers denoting the elements of array A.

Output:
For each testcase, print "Yes" or  "No" whtether it is Pythagorean Triplet or not.

Constraints:
1<=T<=50
 1<=N<=100
 1<=A[i]<=100

Example:

Input:
1
5
3 2 4 6 5

Output:
Yes

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
#include<algorithm>
#include<math.h>
bool Pythagorean_Triplet(int [],int ) ;
int main()
 {
int t,no,i ;
int arr[100] ;
cin>>t ;
while(t--)
{
   cin>>no ;
   for(i=0;i<no;i++)
       cin>>arr[i] ;
     
   if(Pythagorean_Triplet(arr,no))
       cout<<"Yes" ;
   else
       cout<<"No" ;
     
   cout<<endl ;
}
return 0;
}

bool Pythagorean_Triplet(int arr[],int no)
{
    int i,a,b ;
   
    for(i=0;i<no;i++)
        arr[i]=pow(arr[i],2) ;
       
    sort(arr,arr+no) ;
   
    for(i=no-1;i>=0;i--)
    {
        a=0,b=no-1 ;
        while(a<b)
        {
            if(arr[a]+arr[b]==arr[i])
                return true ;
            else if(arr[a]+arr[b]<arr[i])
                a++ ;
            else
                b-- ;
        }
    }
    return false ;
}

---------------------------------------------------------------------------------

Comments

Popular posts from this blog

Count ways to N'th Stair(Order does not matter)

Replace all ‘0’ with ‘5’ in an input Integer

Chocolate Distribution Problem

Remove characters from the first string which are present in the second string

Primality Test ( CodeChef Problem code: PRB01 )