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(n²) 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
X² + Y² = Z². A right angled triangle whose sides are Pythagorean triplet is called a Pythagorean triangle. For example : 3, 4 and 5 are pythagorean triplet(3² + 4² = 5²).

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 X² + Y² = Z².

Time Complexity : O(n³)

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.

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[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.

Time Complexity : O(n²)