Pythagorean Triplets

Moderate

0/80

Average time to solve is 35m

Contributed by

13 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

1
5
1 4 3 2 5

Sample Output 1:

yes

Explanation of the Sample Input1:

One of the possible pythagorean triplet is (3,4,5), as 5*5 = 25 = 3*3 + 4*4.

Sample Input 2:

1
3
1 1 1

Sample Output 2:

no

Hint 1

Hint 2

Hint 3

Implementation, Try all the possible triplets.

Approaches (3)

Approach 1

Approach 2

Approach 3

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.

Time Complexity

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

As we are running 3 nested loops.

Space Complexity

O(1).

As we are using constant extra space.

(100% EXP penalty)

Pythagorean Triplets

Console