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.
#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);
}