Problem of the day
New update is available. Click here to update.
Last Updated: 15 Oct, 2020
Pythagorean Triplets
Moderate
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
Approaches
- 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.
- 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.
- Before jumping into the actual solution , let us observe few things:
- Given two integers a1 and a2 such that a1<a2, then a1^2 < a2^2.
- According to the property: a^2 + b^2 = c^2, it is obvious that a^2 < c^2 , b^2 < c^2 , a<c and b<c.
- Given three integers a1, a2 and b, such that a1<a2 , then a1^2+ b^2 < a2^2 + b^2.
- 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<c and b<c and a^2 + b^2 = c^2.
- 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 <c^2, then we need to increase the sum on the lhs and for that we will increment the pointer βjβ, (as in a sorted array a[j] < a[j+1]) and thus increase x(observation 3).
- 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.
Download our app:
FOLLOW US ON
We accept payments using:
