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

Loop the array for three times and find a, b, and c which are solving equation.

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