# Find Pythagorean Triplets from Array  Difficulty Level Medium
Array

## Problem Statement  We have given an array that contains n integers. We need to find the set of Pythagorean triples from the given array.
Note: Pythagorean triplets condition: a^2 + b^2 = c^2.

## Example  Input

6

[3, 4, 6, 5, 7, 8]

Output

Pythagorean triplets: 3, 4, 5

## Approach 1  We use a brute force algorithm here :

### Algorithm

Step 1: We use 3 loops such that we take a set of 3 different elements from the array.
a.    We run 3 for loops. Such that for every we take all the values b except itself. For every b we take all the values of a.
b.     a, b, c are elements from the array.

Step 2: we run the Pythagorean condition that is a*a + b*b = c*c, for all the sets of (a, b, c). we print them when it is true.
a.    If a^2 + b^2 = c^2, print a, b, c.

### Implementation

#### C++ Program to Find Pythagorean Triplets from Array

```#include <bits/stdc++.h>
using namespace std;
int main()
{

int N;
cin>>N;
int arr[N];
for(int i=0;i<N;i++)
{
cin>>arr[i];
}
int a,b,c;
for(int i = 0; i < N-2; i++)//select an element
{
for(int j=i+1;j <N-1; j++)//select an element in front of the considered element
{
for(int k =i+2; k<N;k++)// this element will be one ahead of the previously selected element in the jus touter loop
{
a = arr[i];
b = arr[j];
c = arr[k];
if(a*a + b*b == c*c) // if the chosen elements satisfy the pythagoras theorem then simply print the three values.
cout << a <<"  "<<b<<"  "<<c<<endl;

}
}
}
return 0;
}```

#### Java Program to Find Pythagorean Triplets from Array

```import static java.lang.Integer.max;
import java.util.Scanner;

class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int arr[] = new int[n];
for(int i=0;i<n;i++)
{
arr[i] = sr.nextInt();
}
int a,b,c;
for(int i=0;i<n-2;i++)//select an element
{
for(int j=i+1;j<n-1;j++)//select an element in front of the considered element
{
for(int k=i+2;k<n;k++)// this element will be one ahead of the previously selected element in the jus touter loop
{
a = arr[i];
b = arr[j];
c = arr[k];
if(a*a + b*b == c*c) // if the chosen elements satisfy the pythagoras theorem then simply print the three values.
System.out.println(a +"  "+b+"  "+c);
}
}
}
}
}```
```6
3 4 6 5 7 8```
`3  4  5`

## Approach 2  ### Algorithm

1.   Sort the given array first using the function sort.
2.  Instead of storing the numbers store the square of each element to directly check the Pythagorean theorem.
3. Take a as the smallest side, for every a check the elements from the array which satisfy the condition (a = c – b). if they satisfy this condition they form Pythagorean triplet as they satisfy the condition a^2 + b^2 = c^2
a.    for all elements in the array from start, store the first element as “a”.
b.    store the last two elements as “b” and “c” respectively.
c.    Check the condition “a = c – b”. if true print the sqrts of a, b, c as a set of Pythagorean triplets.
d.    If “c – b” is greater than “a”, decrease the variable pointing at the larger element(c) so that we are checking for all “c” is this condition true or not. If “c – b” is less than a decrease the variable pointing at the smaller elements so that we are checking for all b is this condition true or not.
e.    continue this loop for all a`s

### Implementation

#### C++ Program to Find Pythagorean Triplets from Array

```#include <bits/stdc++.h>
using namespace std;
int main()
{
int N;
cin>>N;
int arr[N];
for(int i=0;i<N;i++)
{
cin>>arr[i];
}
int a,b,c;
sort(arr,arr+N); //sort the array
for(int i=0; i < N; i++)
arr[i] = (arr[i] * arr[i]); //store the square of each element to directly check the pythagoras theorem

for(int i=0; i<N; i++)
{
int left = N-2 , right = N-1;
a = arr[i]; // first side of the triangle

while(left > i)
{
b = arr[left];
c = arr[right];

int calculated_side = c - b; //if a*a + b*b = c*c then obviously c*c - b*b = a*a , we utilize this to check the condition
if(calculated_side == a)
{
cout << sqrt(a) << "  "  << sqrt(b) << "  " << sqrt(c) << endl;
left++; right--;
}
else if (calculated_side > a) //if side is larger than expected then decrease  the variable pointing at the larger element
right--;
else // if side is smaller than expected then decrease the variable pointing at the smaller element
left--;
}
}
return 0;
}```

#### Java Program to Find Pythagorean Triplets from Array

```import static java.lang.Math.sqrt;
import java.util.Arrays;
import java.util.Scanner;

class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int arr[] = new int[n];
for(int i=0;i<n;i++)
{
arr[i] = sr.nextInt();
}
int a,b,c;
Arrays.sort(arr); //sort the array
for(int i=0;i<n;i++)
arr[i] = (arr[i] * arr[i]); //store the square of each element to directly check the pythagoras theorem
for(int i=0;i<n;i++)
{
int left = n-2 , right = n-1;
a = arr[i]; // first side of the triangle
while(left > i)
{
b = arr[left];
c = arr[right];
int calculated_side = c - b; //if a*a + b*b = c*c then obviously c*c - b*b = a*a , we utilize this to check the condition
if(calculated_side == a)
{
System.out.println((int)sqrt(a) + "  "  + (int)sqrt(b) + "  " + (int)sqrt(c));
left++; right--;
}
else if (calculated_side > a) //if side is larger than expected then decrease  the variable pointing at the larger element
right--;
else // if side is smaller than expected then decrease the variable pointing at the smaller element
left--;
}
}
}
}```
```25
3 8 4 10 6 5 12 13 27 117 165 19 176 169 44 113 24 145 143 51 149 52 173 181 125```
```3  4  5
5  12  13
6  8  10
24  143  145
44  117  125
52  165  173```