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.

Answers


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.


I highly recommend reading http://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple and writing a function that will generate the Pythagorean triples one by one.

Not to give too much of a spoiler, but there are a number of other PE problems that this function will come in handy for.

(I don't consider this giving away too much, because part of the purpose of PE is to encourage people to learn about things like this.)


First, since a is the smallest, you need not to count it up to num, num/3 is sufficient, and even num/(2+sqrt(2)). Second, having a and constraints

a+b+c=num
a^2+b^2=c^2

we can solve this equations and find b and c for given a, which already satisfy this equations and there is no need to check if a^2+b^2=c^2 as you do now. All you need is to check if b and c are integer. And this is done in one loop

for (int a = 1; a < num/3; a++)

Runs in 62 milli seconds

    import time
    s = time.time()
    tag,n=True,1000
    for a in xrange (1,n/2):
        if tag==False:
            break
        for b in xrange (1,n/2):
            if a*a + b*b - (n-a-b)*(n-a-b) ==0:
                print a,b,n-a-b
                print a*b*(n-a-b)
                tag=False
    print time.time() - s

C solution

Warning : solution assumes that GCD(a, b) = 1. It works here but may not always work. I'll fix the solution in some time.

#include <stdio.h>
#include <math.h>

int main(void)
{
  int n = 1000;         // a + b + c = n
  n /= 2;

  for(int r = (int) sqrt(n / 2); r <= (int) sqrt(n); r++)
  {
    if(n % r == 0)
    {
      int s = (n / r) - r;
      printf("%d %d %d\n", r*r - s*s, 2*r*s, r*r + s*s);
      printf("Product is %d\n", (2*r*s) * (r*r - s*s) * (r*r + s*s));
    }
  }

  return 0;
}

Solution uses Euclid's formula for triplets which states that any primitive triple is of form a = r^2 - s^2, b = 2rs, c = r^2 + s^2.

Certain restrictions like sqrt(n / 2) <= r <= sqrt(n) can be added based on the fact that s is positive and r > s.

Warning: you may need long long if the product is large


Definitely not the most optimal solution, but my first instinct was to use a modified 3SUM. In Python,

def problem_9(max_value = 1000):
    i = 0
    range_of_values = [n for n in range(1, max_value + 1)]
    while i < max_value - 3:
        j = i + 1
        k = max_value - 1
        while j < k:
            a = range_of_values[i]
            b = range_of_values[j]
            c = range_of_values[k]
            if ((a + b + c) == 1000) and (a*a + b*b == c*c):
                return a*b*c
            elif (a + b + c) < 1000:
                j += 1
            else:
                k -= 1
        i += 1
    return -1

You say a < b < c, then b must always be bigger than a, so your starting point in the second loop could be b = a + 1; that would lead certainly to fewer iterations.

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

    return -1;
}

In the first given equation, you have three variables a, b, c. If you want to find-out matching values for this equation, you have to run 3 dimension loop. Fortunately there is another equation a+b+c=N where N is known number.

Using this, you can reduce down the dimension to two because if you know two among the three, you can calculate the rest. For instance, if you know a and b, c equals N - a - b.

What if you can reduce one more dimension of the loop? It is possible if you fiddle with the two given equations. Get a pen and paper. Once you get the additional equation with two variables and one constant (N), you will be able to acquire the result in O(n). Solve the two equations a+b+c=n; a^2+b^2=c^2 taking n and a to be constant and solve for b and c:

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int t = in.nextInt();
    for(int a0 = 0; a0 < t; a0++){
        int n = in.nextInt(); 
        int max=-1;
        int multi=0;
       int b=1,c=1;
        for(int i=1;i<=n;i++)
            {
            if(2*(i-n)!=0)
            b=(2*i*n-(n*n))/(2*(i-n));
            c=n-b-i;
            if( (i*i+b*b==c*c)&& i+b+c==n && b>0 && c>=0 && i+b>c && c+i>b && b+c>i)
                {
                multi=i*b*c;
                if(max<multi)
                    max=multi;

            }
        }
        if(max==-1)
        System.out.println(-1);
        else
            System.out.println(max);

    }
}

Need Your Help

Importing ant build.xml in Eclipse

java android eclipse ant

I have an android project that uses ant to build, is it possible to import this ant project in eclipse IDE?

Set date/time using ADB shell

android adb

I´m trying to set the date/time using the ADB shell but the shell only returns the current time.