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

0 comments:

Post a Comment