Trusted answers to developer questions

Educative Answers Team

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.

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.- Increase the position of
`b`

if $b + c < a$. - Decrease the position of
`c`

if $b + c > a$ . - If the sum is equal to
`a`

, then print the square root of the three numbers, increment`b`

, and decrement`c`

. - Repeat the last step for each element
`a`

in the array.

- Increase the position of

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

Copyright Â©2022 Educative, Inc. All rights reserved

RELATED COURSES

View all Courses

Keep Exploring

Related Courses