Given an array of integers, write a function that returns true if there is a triplet (a, b, c) that satisfies a2+b2=c2
Example:
Input: arr[] = {8, 1, 4, 6, 10}
Output: True
There is a Pythagorean triplet (8, 6, 10).
Input: arr[] = {1, 2, 4, 3}
Output: False
There is no Pythagorean triplet.
Approach:
The problem can be solved using ordered maps and unordered maps.
There is no need to store the elements in ordered manner so implementation by unordered map is faster.
We can use unordered map to mark all the values of the given array.
Using two loops, we can iterate for all the possible combinations of a and b,
and then check if there exists the third value c.
If there exists any such value, then there is a Pythagorean triplet.
Below is the implementation of the above approach:
Implementation:
#include <bits/stdc++.h>
using namespace std;
// Returns true if there is Pythagorean triplet in ar[0..n-1]
bool checkTriplet(int arr[], int n)
{ //initializing unordered map with key and value as integers
unordered_map<int ,int> umap;
// Increase the count of array elements in unordered map
for ( int i = 0 ; i < n ; i++ )
umap [ arr[i] ] = umap [ arr[i] ] + 1;
for (int i = 0 ; i < n - 1 ; i++ ) {
for (int j = i + 1 ; j < n ; j++ ) {
//calculating the squares of two elements as integer and float
int p = sqrt ( arr[i] * arr[i] + arr[j] * arr[j] ) ;
float q = sqrt ( arr[i] * arr[i] + arr[j] * arr[j] ) ;
//Condition is true if the value is same in integer and float
//and also the value is present in unordered map
if ( p == q && umap[p] != 0 )
return true ;
}
}
// If we reach here, no triplet found
return false;
}
// Driver Code
int main()
{
int arr[] = { 3, 2, 4, 6, 5 };
int n = sizeof ( arr ) / sizeof ( arr[0] ) ;
if (checkTriplet(arr, n))
cout << "Yes";
else
cout << "No";
}
Output:
Yes
Time Complexity : O(n2)