Question: Find Pythagorean triples in an unsorted array

Or

Find triplets in an integer array A[] which satisfy following condition:

a[i]^2 + a[j]^2 = a[k]^2

Answer: I thought about this and could think of a few optimizations:
1) No need to compute square again and again (need extra space of order N)
2) start for last index of square array.
3) Find 2 elements in square array form beginning to that element, which adds up to it. For doing it in O(n), use solution given in last post.


Pseudo Code:

//Find triplets in an integer array which satisfy a[i]^2 + a[j]^2 = a[k]^2

A[] = 2 1 9 4 8 7 6 3 5 //input

Sort(A); // Sort the input array

//Finally A[] = 1 2 3 4 5 6 7 8 9

//Make an array of squares to avoid compute them again and again
for (i=0; i < n; i++)
{
Sq[i] = A[i]*A[i];
}
//Finally Sq[] =1 4 9 16 25 49 64 81

n = length;
for (i=n; i > 0; i--)
{
res = false;
//Search for 2 numbers in Sq array from 0 to i-1 which
//adds to Sq[i] like we have discussed in last post.
//This will give u a search result in O(n) time.
//Make res as true if we are able to find any triplet.

if (res)
{
 process(triplet);
}
}


Efficiency: Efficiency is
(i) O(nlogn) : for sorting
(ii) O(n^2) : for finding pairs adding equal to A[i]
So total efficeincy is O(n^2)


Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.