Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Code for finding pythagorean triplets

Tags:

java

I am currently attempting this question :

A Pythagorean triplet is a set of three natural numbers, a, b and c, for which a2 + b2 = c2.

For example, 32 + 42 = 9 + 16 = 25 = 52.

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

My code is as follows, I think it should be correct, but the site is telling me my answer is wrong? Can someone help me see the flaws in my logic please?

public class Pythagoras {
    public static void main(String[] args) {
            int sum = 1000;
            int a;
            int product=0;
            for (a = 1; a <= sum/3; a++)
            {
                int b;
                for (b = a + 1; b <= sum/2; b++)
                {
                    int c = sum - a - b;
                    if ( c > 0 && (a*a + b*b == c*c) )
                       System.out.printf("a=%d, b=%d, c=%d\n",a,b,c);
                        product = a * b * c;
                }
            }
            System.out.println(product);
        }
    }
like image 490
Simon Kiely Avatar asked Oct 09 '11 15:10

Simon Kiely


2 Answers

Here are 5 solutions (from slow to fast):

1) Trivial implementation - 732857 microseconds (0.7 seconds)

private static void p1(int sum) {
    for (int a = 0; a <= sum; a++) {
        for (int b = 0; b <= sum; b++) {
            for (int c = 0; c <= sum; c++) {
                if (a < b && b < c && a + b + c == sum
                        && (c * c == a * a + b * b)) {
                    System.out.print(a * b * c);
                    return;
                }
            }
        }
    }
}

2) Limit the lower bound for b & c (establish the order relation) - 251091 microseconds (0.2 seconds)

private static void p2(int sum) {
    for (int a = 0; a <= sum; a++) {
        for (int b = a + 1; b <= sum; b++) {
            for (int c = b + 1; c <= sum; c++) {
                if (a + b + c == sum && (c * c == a * a + b * b)) {
                    System.out.print(a * b * c);
                    return;
                }
            }
        }
    }
}

3) Limit the lower & upper bounds for b & c - 111220 microseconds (0.1 seconds)

private static void p3(int sum) {
    for (int a = 0; a <= sum; a++) {
        for (int b = a + 1; b <= sum - a; b++) {
            for (int c = b + 1; c <= sum - a - b; c++) {
                if (a + b + c == sum && (c * c == a * a + b * b)) {
                    System.out.print(a * b * c);
                    return;
                }
            }
        }
    }
}

4) Limit lower & upper bounds for b and fix value for c - 2625 microseconds

private static void p4(int sum) {
    for (int a = 0; a <= sum; a++) {
        for (int b = a + 1; b <= sum - a; b++) {
            int c = sum - a - b;
            if (c > b && c * c == a * a + b * b) {
                System.out.print(a * b * c);
                return;
            }
        }
    }
}

5) Use Euclid's formula - 213 microseconds

private static void p5(int sum) {
    // a = m^2 - n^2
    // b = 2mn
    // c = m^2 + n^2
    int a, b, c;
    int sqrt = (int)Math.sqrt(sum);
    for (int n = 1; n <= sqrt; n++) {
        for (int m = n+1; m <= sqrt; m++) {
            a = m*m - n*n;
            b = 2*m*n;
            c = m*m + n*n;
            if ( a + b + c == 1000 ) {
                System.out.print(a * b * c);
                return;
            }
        }
    }
}
like image 190
ROMANIA_engineer Avatar answered Oct 18 '22 20:10

ROMANIA_engineer


I think you're missing a set of braces. The indentation leads me to believe the two innermost statements go together but you need curly braces for that to be correct.

if ( c > 0 && (a*a + b*b == c*c) )
{
    System.out.printf("a=%d, b=%d, c=%d\n",a,b,c);
    product = a * b * c;
}

Without the braces product will always contain the product of the last values of a, b, and c. (333 * 500 * 167 == 27805500).

like image 33
Blastfurnace Avatar answered Oct 18 '22 21:10

Blastfurnace