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.

One Thought 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);
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation