Find Pythagorean Triplets in an array in O(N)


Find Pythagorean Triplets in an array


We have an array in which random integers are there. we need to find Pythagorean triplets.
which solves equation a^2 + b^2 = c^2.


Method 1 : Brute Force Method
Loop the array for three times and find a, b, and c which are solving equation.
Time complexity : O(N^3)

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.

You can write and code for this
Best luck
Labels: , ,