Finding Pythagorean Triplet in an array

This post is about finding the pythagorean triplet in an array.

A pythagorean triplet is a group of three numbers in which the sum of the squares of two numbers is equal to the square of a third  number.

for eg:  3,4,5 is a pythagorean triplet as 3(square) + 4(square) = 5(square) ,  9+ 16 =25

Our task is to find three such numbers in an  array consisting many numbers.

One of the  simplest way is to simply run three loops and check if there are three such numbers. but it'd be an O(n3) solution, which is not efficient in case of large inputs.

we can optimize the solution a bit and make it an O(n2) solution.

In fact this is a three sum hard problem and can't be done in less than O(n2).

So how to do it in O(n)?

Here is the approach:

-Find the square of each number

- sort the array

- find the numbers

The following function will return true if such a pair is present in the array:

Code

bool find(int a[], int size)
{
for(int i=0; i<size; i++)
a[i] = a[i] * a[i] ; // squaring each term and storing at the respective position

sort(a, a+size); // sorting the array in o(nlog(n))

for(int i = size-1, i>=2, i--)
{
int l=0, r = i-1;
while(l<r)
{
if(a[l] + a[r] == a[i]))  // check if numbers are found
return 1;
(a[l] + a[r] < a[i])? l++:r--;  // if sum is greater than the last number, we need to decrease the second number else                                                               vice versa
}
}
return 0;
}

we can store the three numbers in an array to return or can simply print them in the function itself.

Thus the overall complexity of the program becomes O(n2).