## Friday, January 17, 2014

### Find all the pythagorean triplets in an array of integer

Given an array a of n integers find all possible Pythagorean triplets from the array.

A Pythagorean triple consists of three positive integers a, b, and c, such that a2 + b2 = c2. this formula is derived from Pythagoras theorem: “For every right angle triangle with side lengths a, b, and c=> a2 + b2 = c2“.

Solution:

Conceptually it is similar to Find Non duplicate pairs that sum to S and 3 SUM problem

```    1) First sort the array, then square each number, now for every element
a[i] in the array find if a pair exist with sum as a[i], this can be
done in O(n) space and O(nlog n) for sorting
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 previous post.
Here our array becomes, a[left+1] to a[right-1], and sum becomes a[left]+a[right].
```

Code :
```FindTriplets(int[] A)
{    //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
int[] Sq = new int[A.length];
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--)
{
bool res = TwoSum( B(i...n-i),A[i],A[n-i])
if (res)
{
print(triplet);
}
//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.

}

public bool TwoSum(int[] B, int a,int b)
{
//return if (a+b) exists in B[]
}
```

Reference - http://stackoverflow.com/questions/10976854/finding-triplets?rq=1