Project Euler - Problem 39

Today's project euler problem was quite interesting:

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p <= 1000, is the number of solutions maximised

First off, for a right triangle with integer values, we know the following:

A = 2*x*n - x^2

B = 2*n^2 - 2*x*n

C = 2*n^2 - 2*x*n + x^2

Where x%2 = 1, and n>x

From this we can craft a simple formula for the perimeters of such triangles:

A+B+C = P = 4*n^2 - 2*x*n

What we need to do then, is for each potential value of x and n, figure out the perimeter and count. I create an integer array, where the index = P, and increment it everytime I get a P < 1000:

// calculate solutions

int[] solutions = new int[1001];

for (int x = 1; x < 1001; x += 2)

{

for (int n = x + 1; ; n++)

{

int p = 4 * n * n - 2 * x * n;

if (p > 1000) break;

for (int m = p; m < 1001; m += p)

{

if (m > 1000) break;

solutions[m]++;

}

}

}

Now it's simple: just find out which perimeter value occurred the most:

// find the maximum count

int ans = 0;

int maxCount = 0;

for (int i = 0; i < 1001; i++)

{

if (solutions[i] > maxCount)

{

maxCount = solutions[i];

ans = i;

}

}

And we're done! The answer turns out to be P = 840. The code executes in < 1ms! Awesomeness!