# Program to Find Pythagorean Triplet in an Array

• Write a program to find Pythagorean triplets in an array.
• Algorithm to find pythagorean triplets in O(n2) time complexity.

Given an integer array of size N we have to find pythagorean triplet in array.

A Pythagorean triplet consists of three positive integers X, Y, and Z, such that
X2 + Y2 = Z2. A right angled triangle whose sides are Pythagorean triplet is called a Pythagorean triangle. For example : 3, 4 and 5 are pythagorean triplet(32 + 42 = 52).
For Example :
```Input Array : 1, 3, 8, 4, 7, 5, 2, 12
Output : (3, 4, 5)
```

Let inputArray be an integer array of size N.

Brute Force Method
• Using three for loop, generate all possible combinations of triples(X, Y, Z) and check whether they satisfy pythagorean triplet equation X2 + Y2 = Z2.
Time Complexity : O(n3)

## C program to find pythagorean triplet in array

```#include <stdio.h>

/* Returns square of a number */
int getSquare(int a){
return a*a;
}

/* prints pythagorean triplets. A, B and C are
Pythagorean triplets if A^2 + B^2 = C^2 */
void printPythagoreanTriplet(int *array, int size) {
int i, j, k, x, y, z;

for(i = 0; i < size; i++) {
for(j = i+1; j < size; j++) {
for(k = j+1; k < size; k++) {
/* Find square of array[i], array[j] and
array[k] and store it in x, y and z*/
x = getSquare(array[i]);
y = getSquare(array[j]);
z = getSquare(array[k]);
/* Check if x, y and z
forms pythagorean triplet */
if (x+y == z || x+z == y || y+z == x){
printf("Pythagorean Triplets Found: [%d, %d, %d]\n",
array[i], array[j], array[k]);
}
}
}
}
}

int main(){
int array = {1, 3, 8, 4, 7, 5, 2, 12};
int i;

printPythagoreanTriplet(array, 8);

return 0;
}
```
Output
```Pythagorean Triplets Found: [3, 4, 5]
```

By Sorting Input Array
• First of all square each element of input Array.
• Now sort squared array using any O(nLogn) average time algorithm like quick sort or merge sort.
• Traverse inputArray and fix one element of triplet. Let's say this element is Z.
• Now the problem reduces to finding two elements whose sum is equal to Z.
• Initialize left and right to 0 and N-1.
• If sum of inputArray[left] and inputArray[right] is equal to Z, then we found one pythagorean triplet.
• Else if sum of inputArray[left] and inputArray[right] is < Z, then increment left index otherwise decrement right index.
• Continue until left < right.
Time Complexity : O(nLogn)

## C program to find pythagorean triplet using sorting

```#include <stdio.h>
#include <math.h>

/* Comparator function for qsort */
int compare(const void *a, const void *b) {
return ( *(int*)a - *(int*)b );
}

int hasSumPair(int *array, int size, int sum) {
int left, right, currentSum;

/* Initialize left and right to first and
last index of array */
left = 0;
right = size-1;
while(left < right) {
currentSum = array[left] + array[right];
/*Check if sun of array[left] and array[right]
is equal to sum */
if(currentSum == sum) {
printf("%d %d", (int)sqrt(array[left]), (int)sqrt(array[right]));
return 1;
} else if(currentSum < sum) {
/* If currentSum < sum, then increase the value
of currentSum by incrementing left index */
left++;
} else {
/* currentSum is greater than sum, decrease
value of currentsum by decrementing right index */
right--;
}
}
return 0;
}

/* prints pythagorean triplets. A, B and C are
Pythagorean triplets if A^2 + B^2 = C^2 */
void printPythagoreanTriplet(int *array, int size) {
int left, right, i;

/* Square each element of array */
for(i=0; i< size; i++)
array[i] = array[i] * array[i];

/* Sort array */
qsort(array, size, sizeof(int), compare);
/* Fix the right most element at index i, and try to \
find two numbers from index 0 to i-1 whose sum is array[i]*/
for(i = size-1; i>= 2; i--){
if(hasSumPair(array, i, array[i])){
printf(" %d\n", (int)sqrt(array[i]));
}
}
}

int main(){
int array = {1, 3, 8, 4, 7, 5, 2, 12};
int i;

printPythagoreanTriplet(array, 8);

return 0;
}
```
Output
```3 4 5
```

By Using Hash Table
• Square each element of input Array.
• Traverse input array and put each squared element of array in hash table.
• Using two for loop, generate all possible pairs of array elements. Let's say current pair is [X,Y].
• Check whether sum of X and Y exists in hash table. If true the we found a pythagorean triplet else continue.
Time Complexity : O(n2)