- Write a program to find Pythagorean triplets in an array.
- Algorithm to find pythagorean triplets in O(n
^{2}) time complexity.

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

A

For Example :**Pythagorean triplet**consists of three positive integers X, Y, and Z, such that**X**. A right angled triangle whose sides are Pythagorean triplet is called a Pythagorean triangle. For example : 3, 4 and 5 are pythagorean triplet(3^{2}+ Y^{2}= Z^{2}^{2}+ 4^{2}= 5^{2}).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
**X**.^{2}+ Y^{2}= Z^{2}

^{3})

## 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[8] = {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.

## 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[8] = {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.

^{2})