Steve P. - 1 year ago 53
Java Question

# Can I make this function more efficient (Project Euler Number 9)?

I just finished Project Euler problem 9 (warning spoilers):

``````A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a^2 + b^2 = c^2

For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.
``````

Here's my solution:

``````public static int specPyth(int num)
{
for (int a = 1; a < num; a++)
for (int b = 2; b < a; b++)
{
if (a*a +b*b == (num-a-b)*(num-a-b))
return a*b*(num-a-b); //ans = 31875000
}

return -1;
}
``````

I can't help but think that there's a solution that involves only one loop. Anyone have ideas? I'd prefer answers using only one loop, but anything that's more efficient than what I currently have would be nice.

``````if a + b +c = 1000
``````

then

`````` a + b + sqroot(a² + b²) = 1000

-> (a² + b²) = (1000 - a - b)²

-> a² + b² = 1000000 - 2000*(a+b) + a² + 2*a*b + b²

-> 0 = 1000000 - 2000*(a+b) + 2*a*b

-> ... (easy basic maths)

-> a = (500000 - 1000*b) / (1000 - b)
``````

Then you try every b until you find one that makes a natural number out of a.

``````public static int specPyth(int num)
{
double a;
for (int b = 1; b < num/2; b++)
{
a=(num*num/2 - num*b)/(num - b);

if (a%1 == 0)
return (int) (a*b*(num-a-b));
}

return -1;
}
``````

EDIT: b can't be higher than 499, because c>b and (b+c) would then be higher than 1000.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download