Pythagorean triplets in an array

Given an array print all the pythagorean triplets.

Answer:


See also : http://en.wikipedia.org/wiki/Pythagorean_triples#Elementary_properties_of_primitive_Pythagorean_triples

#include <vector>
#include <iterator>
#include <algorithm>
#include <stdio.h>
#include <iostream>
using namespace std;


/**
 * See 
 * we can make use of the properties to check that a pythagorean triplet is possible
 * */
bool IsPyTripletPossible(size_t a, size_t b, size_t c)
{
    bool flag = false;
    /*
     * # Exactly one of a, b is odd; c is odd.
     * */
    flag =  (a % 2) + (b % 2) ;
    if (!flag) return flag;
    flag = ((c%2) == 1);
    if (!flag) return flag;
    /*
        # Exactly one of a, b is divisible by 3.
        # Exactly one of a, b is divisible by 4.
        # Exactly one of a, b, c is divisible by 5.
    */
    if ( !(
             ( !(a%3) && (b%3) ) ||
             ( (a%3) && !(b%3) )
            )
       )
        return false;
    if ( !(
             ( !(a%4) && (b%4) ) ||
             ( (a%4) && !(b%4) )
            )
       )
        return false;
    // other tests ignored.
    return true;
}

void PrintPythagorousTriplets(vector &a)
{
    size_t i = 0, j = 1, k = 2;
    size_t lower_bound = 0;
    sort( a.begin(), a.end() );
    while ( k < a.size() )
    {
        if ( (a[k]%2) == 0  )
        {
            // RULE:
            // the hypotenuse cannot be a even number
            ++k;
        }
        else
        {
            size_t k_sq = a[k] * a[k];
            i = lower_bound;
            j = k - 1;
            bool found = false;
            while ( i < j )
            {
                size_t sq = a[i]*a[i] + a[j]*a[j];
                if ( sq == k_sq )
                {
                    printf(" %d, %d, %d \n", a[i], a[j], a[k]);
                    found = true;
                    break;
                    // break, because there can be one and only one
                    // py triplet, (because there is only one way to draw
                    // a triangle)
                }
                else if ( sq < k_sq )
                    ++i;
                else if ( sq > k_sq )
                    --j;
            }
            if ( found )
            {
                // RULE :
                // There are no Pythagorean triplets in which the hypotenuse and 
                // one leg are the legs of another Pythagorean triple.
                // so the next search can start from the hypotenuse of the current 
                // triplet
                lower_bound = i;
            }
            ++k;
        }
    }
}

int main( int argc, char* argv[] )
{
    if ( argc == 1 ) return 0;
    else
    {
        vector a(argc-1);
        for ( int i = 1; i <= argc-1; ++i)
            a[i-1] = atoi(argv[i]);
        cout << "Input :" << endl;
        copy ( a.begin(), a.end(), ostream_iterator(cout, " "));
        cout << endl;
        PrintPythagorousTriplets(a);

    }
    return 0xabcdef;

}