Wednesday, August 27, 2014

Finding all Pythagorean triples in an array

Given an array of unique elements, Write a program to print all Pythagorean triples in it.

A Pythagorean triple is a set of three numbers such that square of one number is the sum of squares of the other two.

For example (3,4,5) is Pythagorean triple because 52 = 32 + 42

Consider the array {5, 6, 3, 10, 4, 2, 1 , 8, 7} 
It contains two Pythagorean triples (3,4,5) and (6,8,10)

An obvious solution to this problem could be examine all possible triples in the array and check if it satisfies the above property.
But this solution takes O(n3) time.

We can do better than this if we first square all the elements and sort them in descending order.

Then this problem is simplified to finding three indices in the array i,j,k such that arr[i] = arr[j]+arr[k]

The algorithm is as follows.

For each array[i] 0 <= i < n-2

     index1 <- i+1
     index2 <- n-1
     While index1 < index 2
        If array[i] = array[index1] + array[inde2]
           Print Triple
        If array[i] <  array[index1] + array[inde2]

Here is the implementation of the above in C++. It takes O(n log n) for sorting and O(n2) for the actual algorithm. So the effective time complexity for this problem is

Solution 2:
Alternatively you can use a Hash set to store all the square values. Then examine all possible pairs in the array to check if sum of their squares exists in the set.
This approach also takes O(n2) time but uses O(n) extra space. 
Note: The hash_set implementation is available only in Visual studio 10 compiler and above. In C++ 11 standard it is mentioned as unordered_set. If we use normal set, the time complexity will become O(n2 log n).