Related Tags

triplet
pythagorean
array
c++
python

# How to find Pythagorean triplets in an array

A Pythagorean triplet is a set {a, b, c} such that $a^2 = b^2+ c^2$. The user is provided with an array of integers and has to identify all the possible sets of Pythagorean triplets.

## Algorithm

The naive approach here would be to run three nested for loops to try all possible triplets in an array. However, the complexity of such a solution would be $O(n^3)$.

Instead, we can solve the problem in $O(n^2)$ by sorting the array in ascending order, first.

The steps involved would be:

• Square every element in the input array and then sort it in ascending order.
• Since the array now contains squares, the new equation for triplet becomes $a = b + c$. Fix a to be the last element of this sorted array, since a will always have the largest value of the three numbers.
• Fix b as the first element of the sorted array and c as the element right before element a. Since numbers are positive and the array is sorted, $b < a$ and $c < a$. To find triplets, run a loop that increases b from $1$ to $n$, and decreases c from $n$ to $1$ at the same time until they meet.
1. Increase the position of b if $b + c < a$.
2. Decrease the position of c if $b + c > a$ .
3. If the sum is equal to a, then print the square root of the three numbers, increment b, and decrement c.
4. Repeat the last step for each element a in the array.

The following slides help us to visualize this algorithm:​

1 of 11

## Code

#include <algorithm>
#include <iostream>
#include <math.h>
using namespace std;

void findTriplet(int arr[], int n)
{
// Step 1
for (int i = 0; i < n; i++)
arr[i] = arr[i] * arr[i];

// Sort array elements
sort(arr, arr + n);

// Step 2 and Step 3
for (int i = n - 1; i >= 2; i--) {  // Fixing a
int b = 0;    // Fixing b
int c = i - 1;    // Fixing c
while (b < c) {
// A triplet found
if (arr[b] + arr[c] == arr[i]){
cout << "Triplet: "<< sqrt(arr[b]) <<", "<< sqrt(arr[c]) <<", "<< sqrt(arr[i])<<"\n";
b++;
c--;
}

// Else either move 'b' or 'c'
else if (arr[b] + arr[c] < arr[i]) {
b++;
}
else {
c--;
}
}
}
}

// Driver code
int main()
{
int arr[] = { 3, 1, 4, 6, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
findTriplet(arr, n);
return 0;
} 

RELATED TAGS

triplet
pythagorean
array
c++
python