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