## Pythagorean Triples

Posted by sanstechbytes on July 10, 2011

A quick background on properties of Pythagorean triples can be got from here and here.

When I was browsing through topics in algorithm forum on stackoverflow.com , I found , sort of, an interesting challenge in finding Pythagorean Triples in the given array, saying: Can’t be achieved in no better than O(n*n) time complexity(a unanimous opinion). This enthused me to attempt writing a faster than O(n*n) algo, but after much analysis and code completion, I couldn’t help joining the participants. In below lines, the code snippet follows. I wonder, if any algorithm enthusiast or researcher could point me to a faster algorithm than O(n*n), if there exists any.

Follow comments in-line to help yourself understand the algorithm used. This algorithm achieves O(k*n*n) time complexity where k is nearly equal to n/3 in most cases. For brevity, it’s an O(n*n) algo.

// O(n+n*log n+k*n*n) = O(k*n*n)= O(n*n) algo where k is nearly n/3 in

// most cases

// Returns the number of triples found.

// Returns

// -1, when n < 3,

// 1 when n = 3 and/or a triple is found and

// 0 when no triple found

public static int pythtriples(int[] pyth) {

int n = pyth.length;

// No duplicate removal algo is used before sort, to avoid the cost of

// O(n),as this will be taken care of below,in for loop.

// (Trivial) Shifting mechanism should be used in

// array with new length in-place(trivial)in case,

// either the element occurring in multiple places is 0 or neg integer

// Square all the numbers – O(n) time complexity.

for (int i = 0; i < n; i++) {

pyth[i] = pyth[i] * pyth[i];

}

// Sort them – O(n * log n) time complexity

Arrays.sort(pyth);

if (n < 3) {

return -1; // error : No of elements must be >= 3

}

// Simple case

if (n == 3) {

if (pyth[2] == pyth[1] + pyth[0])

return 1;

else

return 0;

}

// Compare pair-wise: if(a[i] == (a[j] + a[k]) then, it’s a triple),

// k<i, j<i

// O(k* n * n) time complexity, where k is nearly n/3, can be

int triples = 0, foundtripleLarge = 0;

for (int i = 2; i < n; i++) {

for (int j = 0; j < i; j++) {

for (int k = i – 1; k >= 0; k–) {

// If already found, don’t compare again for 3SUM. Avoids

// unnecessary check for duplicates

if (foundtripleLarge == pyth[i]) {

break;

}

if (pyth[i] == (pyth[j] + pyth[k])) {

System.out.println(“triples found: ” + pyth[i] + ” = ”

+ pyth[j] + ” + ” + pyth[k]);

triples++; // Counter for triples

foundtripleLarge = pyth[i];

break;

}

}

}

}

return triples;

}

Math: The pair-wise comparison follows: 1^2 + 2^2 + 3^2 + …..+n^2 = n(n+1)(2n+1)/6, nearly equal to 3n^2, same as our O(kn^2) algo above!

## Leave a Reply