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.
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