Pythagorean Triplet

Task: Given an array of integers, If a, b, c are integers in an array and satisfies the Pythagorean formulae : a^2 + b^2 = c^2 then print Yes else print No.

Example:

Input:

1

5

3 2 4 1 5

Output:

Yes // 3,4, and 5 are Pythagorean Triplets.

---

Here is the Code:

Program in C++:

1. #include<iostream>
2. #include<bits/stdc++.h>
3. using namespace std;
4. string pythagoreanTriplet(int *a,int n)
5. {
6.     set<int> s;
7.     for(int i=0;i<n;i++)
8.     {
9.         a[i]=a[i]*a[i];
10.         s.insert(a[i]);
11.     }
12.     sort(a,a+n);
13.     // 4 9 16 25 36
14.     for(int i=n-1;i>=2;i--)
15.     {
16.         int j=0;
17.         while(j<i)
18.         {
19.             if(s.find(a[i]-a[j])!=s.end()) return "Yes";
20.             auto k = s.find(a[i]-a[j]);
21.             if(*k+a[j]>a[i]) break;
22.             j++;
23.         }
24.     }
25.     return "No";
26. }
27. int main()
28.  {
29. int t;
30. cin>>t;
31. while(t--)
32. {
33.     int n;
34.     cin>>n;
35.     int a[n];
36.     for(int i=0;i<n;i++)
37.     {
38.         cin>>a[i];
39.     }
40.     cout<<pythagoreanTriplet(a,n)<<endl;
41. }
42. return 0;
43. }

---

Here is the Video: