A Pythagorean triplet is a set {a, b, c} such that . The user is provided with an array of integers and has to identify all the possible sets of Pythagorean triplets.
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 .
Instead, we can solve the problem in by sorting the array in ascending order, first.
The steps involved would be:
a
to be the last element of this sorted array, since a
will always have the largest value of the three numbers.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, and . To find triplets, run a loop that increases b
from to , and decreases c
from to at the same time until they meet.
b
if .c
if .a
, then print the square root of the three numbers, increment b
, and decrement c
.a
in the array.The following slides help us to visualize this algorithm:
#include <algorithm>#include <iostream>#include <math.h>using namespace std;void findTriplet(int arr[], int n){// Step 1for (int i = 0; i < n; i++)arr[i] = arr[i] * arr[i];// Sort array elementssort(arr, arr + n);// Step 2 and Step 3for (int i = n - 1; i >= 2; i--) { // Fixing aint b = 0; // Fixing bint c = i - 1; // Fixing cwhile (b < c) {// A triplet foundif (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 codeint main(){int arr[] = { 3, 1, 4, 6, 5 };int n = sizeof(arr) / sizeof(arr[0]);findTriplet(arr, n);return 0;}
Free Resources