Find Pythagorean triples in an unsorted array

Find Pythagorean triples in an unsorted array | PROGRAMMING INTERVIEWS
Question: Find Pythagorean triples in an unsorted array
Find triplets in an integer array A[] which satisfy following condition:
a[i]^2 + a[j]^2 = a[k]^2
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. 

1. //Find triplets in an integer array which satisfy a[i]^2 + a[j]^2 = a[k]^2  
2.   
3. A[] = 2 1 9 4 8 7 6 3 5 //input  
4.   
5. Sort(A); // Sort the input array  
6.   
7. //Finally A[] = 1 2 3 4 5 6 7 8 9  
8.   
9. //Make an array of squares to avoid compute them again and again  
10. for (i=0; i < n; i++)  
11. {  
12. Sq[i] = A[i]*A[i];  
13. }  
14. //Finally Sq[] =1 4 9 16 25 49 64 81  
15.   
16. n = length;  
17. for (i=n; i > 0; i--)  
18. {  
19. res = false;  
20. //Search for 2 numbers in Sq array from 0 to i-1 which  
21. //adds to Sq[i] like we have discussed in last post.  
22. //This will give u a search result in O(n) time.  
23. //Make res as true if we are able to find any triplet.  
24.   
25. if (res)  
26. {  
27.  process(triplet);  
28. }  
29. }  

http://yuanhsh.iteye.com/blog/2182082

Method 2 : Using Hash Map to search.

1) Create two loops and find all pairs.
  2) Find +C, -C = SquareRoot ( A^2 + B^2)
  3) Using Hash find whether C is present in Array or not.
  4) If C is present print Triplet A, B, C 
  5) Else continue till both loop completes.

Method 3 : Using Maths 

We know that 
a = m^2 - n^2, b = 2mn, c = m^2 + n^2
From here you can get clue.. 
If not .. read further.

1)Sort the array in O(N log N) time.
2)For each element B, find the prime factorization. such that  
b = 2mn , m > n. m and n are prime
3)Calculate C = m^2 + n^2 , A= m^2 - n^2
4)With Hashmap find If C and A are in Array. Then Print Triplet C,A,B
5)Else Continue.

Explanation :

Consider Array : {3,6,8,5,10,4,12,14}

Step 1) 
Finding prime factorization such that b=2mn.
3 - not possible.
6 - 2*1*3 so m=3, n=1
8 - 2*2*2 so m=2,n=2 (not allowed , as they need to be co-prime)
5 - not possible
10 - 2*1*5 so m=5, n=1
4 - 2*1*2 so m=2, n=1 ...

Step 2) 

6 - 2*1*3 so m=3, n=1 m^2 + n^2 = 10 , m^2 - n^2 = 8 , 
both numbers are present in array can be found in O(1) 
with Hash.
    C = 10, A =8 and B = 6

=> similarly for 3,4,5 we can find 
m=2,n=1, B=4, C=5, A=3.

http://comproguide.blogspot.com/2014/08/finding-all-pythagorean-triples-in-array.html
void printPythagoreanTriples( vector<int> & arr )
{
if( arr.size() < 3 )
{
cout << "Input too small!" << endl;
return;
}
sort( arr.begin(), arr.end(), greater<int>());

//square each number in array; using STL transform() algorithm
transform( arr.begin(), arr.end(), arr.begin(), getSquare );

int i;
for( i = 0; i < arr.size()-2; i++ )
{
int start = i+1, end = arr.size()-1;
while(start < end)
{
if( arr[i] == arr[start] + arr[end] )
{
cout <<(int)sqrt(arr[i]*1.0) << " ";
cout <<(int)sqrt(arr[start]*1.0) << " ";
cout <<(int)sqrt(arr[end]*1.0) << endl;
start++;
end--;
}
else if( arr[i] < arr[start]+arr[end] )
{
start++;
}
else
{
end--;
}
}
}
}
http://www.dsalgo.com/2013/04/find-pythagorean-triplets-in-array.html

 private static void findPythagoreanTriplets(int[] arr) {
  HashSet squares = new HashSet();
  for (int num : arr)
   squares.add((long) num * num);
  for (int i = 0; i < arr.length - 1; ++i)
   for (int j = i + 1; j < arr.length; ++j) {
    long square = (long) arr[i] * arr[i] + (long) arr[j] * arr[j];
    if (squares.contains(square)) {
     System.out.println(arr[i] + "," + arr[j] + ","
       + (long) Math.sqrt(square));
    }
   }
 }

http://codes-to-problem.blogspot.com/2012/11/finding-pythagorean-triplets-in-array.html

http://tech-queries.blogspot.com/2010/12/sum-of-2-nos-in-array-equal-to-given.html
Efficiency: if input array A is sorted then O(N).
else O(NlogN) coz of sorting time NlogN.

1. bool sum_euqal_to_N(int A[], int N)  
2. {  
3.  int start = 0;  
4.  int end = MAX-1;  
5.    
6.  //check for boundary conditions  
7.  if ((A[start]+A[start+1]) > N)  
8.   return false;  
9.    
10.  if ((A[end]+A[end+1]) < N)  
11.   return false;  
12.    
13.    
14.  while (end > start)  
15.  {  
16.   if ((A[start] + A[end]) < N)  
17.    start++;  
18.   else if ((A[start] + A[end]) == N)  
19.   {  
20.    cout << A[start] << " " << A[end] << endl;  
21.    return true;  
22.   }  
23.   else  
24.    end--;  
25.  }  
26.    
27.  return false;  
28. }  

http://www.geeksforgeeks.org/find-pythagorean-triplet-in-an-unsorted-array/

Given an array of integers, write a function that returns true if there is a triplet (a, b, c) that satisfies a2 + b2 = c2.

O(N^2)

   static boolean isTriplet(int arr[], int n)

    {

        // Square array elements

        for (int i=0; i<n; i++)

            arr[i] = arr[i]*arr[i];

  

        // Sort array elements

        Arrays.sort(arr);

  

        // Now fix one element one by one and find the other two

        // elements

        for (int i = n-1; i >= 2; i--)

        {

            // To find the other two elements, start two index

            // variables from two corners of the array and move

            // them toward each other

            int l = 0; // index of the first element in arr[0..i-1]

            int r = i-1; // index of the last element in arr[0..i-1]

            while (l < r)

            {

                // A triplet found

                if (arr[l] + arr[r] == arr[i])

                    return true;

  

                // Else either move 'l' or 'r'

                if (arr[l] + arr[r] < arr[i])

                   l++;

                else

                   r--;

            }

        }

  

        // If we reach here, then no triplet found

        return false;

    }

O(N^3) - A simple solution is to run three loops, three loops pick three array elements and check if current three elements form a Pythagorean Triplet.

   static boolean isTriplet(int ar[], int n)

    {

        for (int i=0; i<n; i++)

        {

            for (int j=i+1; j<n; j++)

            {   

                for (int k=j+1; k<n; k++)

                {

                    // Calculate square of array elements

                    int x = ar[i]*ar[i], y = ar[j]*ar[j], z = ar[k]*ar[k];

  

                    if (x == y + z || y == x + z || z == x + y)

                        return true;

                }

            }

        }

  

        // If we reach here, no triplet found

        return false;

    }

Read full article from Find Pythagorean triples in an unsorted array | PROGRAMMING INTERVIEWS