# Pythagorean triplets in an array

Given an array of integers . Write an algorithm to find all the Pythagorean triples.

Eg : i/p : int arr[ ] = {1,3,4,5,6,7,8,10,11} o/p: Print 3,4,5 and 6,8,10

Solution:

Steps:

(1) First square each element.

(2) Sort the array in ascending order. This takes O(n log n).

(3) Now consider each element a[ i ]. If a[ i ] = a[j]+a[k], then, since numbers are positive and array is now sorted, k < i and j < i. To find such indexes, run a loop that increases j from 1 to i, and decreases k from i to 0 at the same time, until they meet. Increase j if a[j]+a[k] < a[i], and decrease k if the sum is greater than a[i]. If the sum is equal, that’s one of the answers, print it, and shift both indexes. This takes O(i) operations.
Repeat step 2 for each index i. This way you’ll need totally O(n^2) operations, which will be the final estimate.

Code is left for the readers.

### 0 Thoughts on “Pythagorean triplets in an array”

1. Rizwana on June 7, 2014 at 8:43 am said:

#include
#include
main()
{
int arr[10]={1,3,4,5,6,7,8,10,11};

int i,j,k,count=0;

for(i=0;i<10;i++)
{
for(j=i+1;j<10;j++)
{
for(k=j+1;k<10;k++)
{
if(arr[i]*arr[i]+arr[j]*arr[j]==arr[k]*arr[k])
{count++ ;
printf("\npossible triangles %d,%d,%d",arr[i],arr[j],arr[k]);

}

}
}
}
printf("\n minimum number of possible triangles %d",count);
}