Pythagorean Triplets
You are given an array of n integers (a1, a2,....,an), you need to find if the array contains a pythagorean triplet or not.

An array is said to have a pythagorean triplet if there exists three integers x,y and z in the array such that x^2 + y^2 = z^2.

Note

1. The integers x,y and z might not be distinct , but they should be present at different locations in the array i.e if a[i] = x, a[j] = y and a[k] = z, then i,j and k should be pairwise distinct. 2. The integers a,b and c can be present in any order in the given array.

Input Format:

The first line contains a single integer t - the number of test cases. Each test case consists of 2 lines as follows: The first line of each test case will contain the integer n, denoting the total number of elements in the array. The second line of each test case will contain n space-separated integers a1,a2,....,an , where ai is the ith element of the array..

Output Format:

For each test case, print “yes”, if the array contains a pythagorean triplet,”no” otherwise.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Pythagorean Triplets

You are given an array of n integers (a1, a2,....,an), you need to find if the array contains a pythagorean triplet or not.

An array is said to have a pythagorean triplet if there exists three integers x,y and z in the array such that x^2 + y^2 = z^2.

Note

1. The integers x,y and z might not be distinct , but they should be present at different locations in the array i.e if a[i] = x, a[j] = y and a[k] = z, then i,j and k should be pairwise distinct.
2. The integers a,b and c can be present in any order in the given array.

Input Format:

The first line contains a single integer t -  the number of test cases. Each test case consists of 2 lines as follows:
The first  line of each test case will contain the integer n, denoting the total number of elements in the array.
The second line of each test case will contain n space-separated integers a1,a2,....,an ,  where ai is the ith element of the array..

Output Format:

For each test case, print “yes”, if the array contains a pythagorean triplet,”no” otherwise.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <=  T <= 10
3 <=  N <= 10^3
1 <= a[i] <= 10^4 

Time Limit: 1sec

Accepted Answer

Approach :
1) I solved it in O(N^2) approach.
2) Sort the array.
3) Initially map all the elements of the array to their index in a Hash Map or a Hash Set.
4) Now , run 2 for loops and for every x^2 + y^2 ,check if there exists a z^2 s.t x^2+y^2=z^2 and the index of z^2 is
different than both the indices of x and y.

Accepted Answer

Brute Force

One simple naive solution is to try every possible triplet present in the array as a candidate for the pythagorean triplet.
So, we simply run three nested loops, and pick three integers and check if they follow the property given in the problem statement( i.e for three integers a,b and c a^2 b^2 = c^2).
If we find any required triplet, we return true. Otherwise, if we can't find any valid triplet, we return false.

Space Complexity: O(1)Explanation:

O(1).

As we are using constant extra space.

Time Complexity: O(1)Explanation:

O(n^3) , where n is the number of integers in the array.

As we are running 3 nested loops.

Accepted Answer

HASHMAP

Let us assume that the maximum element in the array is ‘mx’, now we know that if there is a valid pythagorean triplet (a,b,c) in the array , then a<=mx, b<=mx, and c<=mx.
Thus, we can iterate over all possible combinations of ‘a’ and ‘b’ using two loops, which will run from 1 to ‘’mx’, and check that if there exists a valid ‘c’ in the array for the current ‘a’ and ‘b’.
To check for valid ‘c’, we can store the frequency of all the elements of the array, in a hashmap, and while checking compute the square root of a^2 + b^2, and check if this square root is an integer and it is present in the hashmap or not. If yes , return true.

Space Complexity: O(1)Explanation:

O(n), where n is the total number of elements in the array.

As we are using either a frequency array, or a hashmap to store the elements of the array, space complexity is proportional to the size of the input array.

Time Complexity: O(1)Explanation:

O(maxn*maxn) , where maxn is the value of the maximum integer in the array.

We are running two nested loops and each one of them takes O(maxn) time.

Accepted Answer

Sorting

Before jumping into the actual solution , let us observe few things:

Given two integers a1 and a2 such that a1
According to the property: a^2 + b^2 = c^2, it is obvious that a^2 < c^2 , b^2 < c^2 , a
Given three integers a1, a2 and b, such that a1
Given three integers a1, a2 and b, such that a1>a2 , then a1^2+ b^2 > a2^2 + b^2.

Let us assume that there are three integers a, b and c in the array such that a^2 + b^2 = c^2.
Now by using the above four observations, let us assume that in the given array the integers are in non-descending order. If we fix the rhs(right hand side) of the property i.e c^2, then by observation 2 , it is clear that if the integer c is present at ith index in the array, then both integers a and b will be present before c, that is their indices will be less than ‘i’.
So let us first sort the array in non-decreasing order. Now in every iteration, fix the current element as a possible candidate for ‘c’. Let c be present at ith index of the array , such that there are at least two elements before c. Now we just need to find two elements a and b such that a
So we will use two pointers, one will start from the beginning and the other will start from (i-1)th index as all elements less than c are in this range.
Let the two pointers be ‘j’ and ‘k’ , such that j is starting from the beginning. Now while j is less than k, let us assume that x= a[j] and y = a[k]. Now there are three possibilities:

If x^2 + y^2 = c^2, then we have found a valid triplet and we simply return true.
Else if x^2 + y^2
Else x^2 + y^2 > c^2, then to decrease the sum on the lhs, we will decrement the pointer ‘k’ ( as a[k] > a[k-1]) and thus decrease y(observation 4).

Thus for every possible ‘c’, we can find the valid pair of a and b in linear fashion.

Space Complexity: O(1)Explanation:

O(1).

As we are using constant extra space.

Time Complexity: O(1)Explanation:

O(n^2) , where n is the number of integers in the array.

For every possible candidate for c, we can find if there are valid a and b in O(n) time. Thus the complexity will be O(n*n).

You are given an array of n integers (a1, a2,....,an), you need to find if the array contains a pythagorean triplet or not.

An array is said to have a pythagorean triplet if there exists three integers x,y and z in the array such that x^2 + y^2 = z^2.

Note

Input Format:

Output Format:

Note:

Constraints:

Top Ernst & Young Associate Software Engineer interview questions & answers

Popular interview questions of Associate Software Engineer

Top HR questions asked in Ernst & Young Associate Software Engineer