Friday, November 27, 2015

LinkedIn: Find Pythagorean Triplets in an array

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


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.

2 comments:

  1. Hi, can you confirm that the runtime efficiency is O(N^2)?

    Thanks,
    Guy

    ReplyDelete
  2. With method 2, the runtime complexity is definitely O(N^2). It takes a linear amount of time to loop through the array and add each element to a HashMap, but that is trumped by the quadratic time it takes to search every single possible pair of elements in the array. It requires double for loops to do this:

    for (int i = 0; i < array.length; i++) {
    for (int j = i + 1; j < array.length; j++) {
    int value1 = Math.sqrt(Math.pow(array[i], 2) + Math.pow(array[j], 2));
    int value2 = value1 * -1;
    if (hashmap contains value1 or value2 and their indices are not equal
    i or j) {
    // this is a good triplet of values
    }
    }
    }

    ReplyDelete