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 ;
}
---------------------------------------------------------------------------------
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
Post a Comment