# Find Pythagorean Triplets from Array

Difficulty Level Medium
ArrayViews 3055

## 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`

### Complexity Analysis to Find Pythagorean Triplets from Array

#### Time complexity

O(n^3) where n is the size of the array. Here we check the condition for every possible triplet.

#### Space Complexity

O(1) because we use a few variables to calculate the answer.

## 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```

### Complexity Analysis to Find Pythagorean Triplets from Array

#### Time complexity

O(n^2) where n is the size of the array. Here we use two pointer methods for each I value. This leads us to O(N*N) time complexity.

#### Space Complexity

O(1) because we use a few variables to calculate the answer.

References

Translate »