Project Euler #9: Finding Pythagorean triplets with a given sum

Question

Problem statement:

A Pythagorean triplet is a set of three natural numbers, A < B < C, for which, A² + B² = C². Given a number N, check if there exists any Pythagorean triplet for which A + B + C = N.

public class SpecialPythagoreanTriplet {

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int t = scan.nextInt();
    int n=0, i=0, j=0, a=0, b=0, c=0;
    
    while(t!=0) {
        n = scan.nextInt();
        a=0; b=0; c=0;
        for(i=1; i<n; i++)
            for(j=(i+1); j<=n; j++) {
                //These two loops run to take a pair of numbers. j=(i+1) to avoid repetitions in the future.
                if(isSquare((i*i) + (j*j))) //check if a number is a square
                    if(((int)Math.sqrt((i*i)+(j*j)) + i + j) == n) {
                        a = i;
                        b = j;
                        c = (int)Math.sqrt((i*i)+(j*j));
                    }
            }
        if(c==0)
            System.out.println(-1);
        else
            System.out.println(a*b*c);
        t--;
    }
    scan.close();
}

static boolean isSquare(double t) { 
    int a = (int)Math.sqrt(t);
    if(a*a == t)
        return true;
    else
        return false;
}
}

I was working on this program in ProjectEuler and Hackerrank consecutively. It ran perfectly for the input of 1000 and got accepted in Project Euler. But it is giving Terminated Due to Timeout error in most of the cases in Hackerrank.

How can I optimize it more to evade this error?

Answer 1

Program terminates due to timeout because of high time complexity, \$O(t*n*n)\$.

Complexity of this program can be reduced to \$O(t)\$ by precomputing and saving the results to avoid repeated computation.

Repeated computation for finding combination of two numbers ( i and j ) can to reduced to execute only once, for a fixed number of times independent of 'n'.

Here is a complete implementation in java:

import java.io.*;
import java.math.*;

public class Solution {

    public static void main(String[] args) {
       BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
       try{

           //precomputation
           int save[] = new int[3001];

            for(int i=1; i<3001; i++){
               int iSqr = i*i;
               for(int j=i+1; j<3001; j++){

                   double x = Math.sqrt(iSqr + j*j);
                   if(x == Math.floor(x)){
                        int sum     = i+j+(int)x;
                        int product = i*j*(int)x;
                        if((sum < 3001) && (product > save[sum]))
                            save[sum] = product;
                   }
               }              
           }

           int t = Integer.parseInt(stdin.readLine());

           while(t-- > 0){
               int n = Integer.parseInt(stdin.readLine());
               if(save[n] == 0)
                   System.out.println(-1);
               else
                   System.out.println(save[n]);
           }
       }
       catch(Exception e){

       }
    }
}

Answer 2

Reorganising the code

In general, it is a good idea to have your logic computing result and your logic handling output/input as independant as possible. This makes things easier to test, easier to understand and thus easier to optimise. In problems based on Project Euler, this is usually a fairly simple task because the problems are described in such a way that they need little or no input and return a number.

In your case, you could write something like:

import java.util.Scanner;

public class SpecialPythagoreanTriplet {

    public static int getProductForPythagoreanTriplerOfPerim(int n)
    {
        int i=0, j=0, a=0, b=0, c=0;
        for(i=1; i<n; i++)
            for(j=(i+1); j<=n; j++) {
                //These two loops run to take a pair of numbers. j=(i+1) to avoid repetitions in the future.
                if(isSquare((i*i) + (j*j))) //check if a number is a square
                    if(((int)Math.sqrt((i*i)+(j*j)) + i + j) == n) {
                        a = i;
                        b = j;
                        c = (int)Math.sqrt((i*i)+(j*j));
                    }
            }
        return (c==0) ? -1 : a*b*c;
    }

    public static void main(String[] args) {
        if (false) // interactive
        {
            Scanner scan = new Scanner(System.in);
            for (int t = scan.nextInt(); t!=0; t--) {
                System.out.println(getProductForPythagoreanTriplerOfPerim(scan.nextInt()));
            }
            scan.close();
        }
        else // hardcoded
        {
            System.out.println(getProductForPythagoreanTriplerOfPerim(25) == -1);
            System.out.println(getProductForPythagoreanTriplerOfPerim(1000) == 31875000);
            System.out.println(getProductForPythagoreanTriplerOfPerim(30000) == 1197129472);
        }
    }

    static boolean isSquare(double t) {
        int a = (int)Math.sqrt(t);
        if(a*a == t)
            return true;
        else
            return false;
    }
}

Improving the code quality

Then, a few things you could do to improve your code quality: - remove useless comment - put brackets around any block containing more than 1 line of code even if this is not required - define variables in the smallest possible scope - factorise out expressions written and computed multiple times.

You'd get something like:

public static int getProductForPythagoreanTriplerOfPerim(int n)
{
    int a=0, b=0, c=0;
    for (int i=1; i<n; i++) {
        for (int j=i+1; j<=n; j++) {
            //These two loops run to take a pair of numbers. j=(i+1) to avoid repetitions in the future.
            int squareCand = i*i + j*j;
            if (isSquare(squareCand)) {
                int squareRoot = (int)Math.sqrt(squareCand);
                if (squareRoot + i + j == n) {
                    a = i;
                    b = j;
                    c = squareRoot;
                }
            }
        }
    }
    return (c==0) ? -1 : a*b*c;
}

Optimising the code

Once you've done this. You do not really need the function isSquare anymore. For performance reason, it would even be a good idea to get rid of it in order not to compute square roots multiple times.

public static int getProductForPythagoreanTriplerOfPerim(int n)
{
    int a=0, b=0, c=0;
    for (int i=1; i<n; i++) {
        for (int j=i+1; j<=n; j++) {
            //These two loops run to take a pair of numbers. j=(i+1) to avoid repetitions in the future.
            int squareCand = i*i + j*j;
            int squareRoot = (int)Math.sqrt(squareCand);
            if (squareRoot*squareRoot == squareCand) {
                if (squareRoot + i + j == n) {
                    a = i;
                    b = j;
                    c = squareRoot;
                }
            }
        }
    }
    return (c==0) ? -1 : a*b*c;
}

Then it is clear that the conditions can be rewritten:

           if (squareRoot*squareRoot == squareCand &&
                squareRoot == n - i - j) {
                    a = i;
                    b = j;
                    c = squareRoot;
            }

Then you can use this in order not to compute any squareRoot:

            int squareRootCand = n - i - j;
            int squareCand = i*i + j*j;
            if (squareRootCand*squareRootCand == squareCand) {
                    a = i;
                    b = j;
                    c = squareRootCand;
            }

Also it is even clearer that we want i + j <= n. Because i < j, we also have 2 * i < n. Thus, the loop boundaries can be rewritten:

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

I think a more precise analysis of the mathematical property would lead to a smaller search space. In fact, because i corresponds to the smallest side, we could write: 3 * i < nand i + 2j < n.

Warning: from here, it's just me trying to apply random (and simple) math operations with no promise whatsoever that things will get better.

By limiting the number of times sub-expressions are computed, one could write (but I do not find this very beautiful):

    int a=0, b=0, c=0;
    for (int i=1; 3*i < n; i++) {
        int i2 = i*i;
        int rem = n-i;
        for (int j=i+1; 2*j<=rem; j++) {
            int squareRootCand = rem - j;
            int squareCand = i2 + j*j;
            if (squareRootCand*squareRootCand == squareCand) {
                    a = i;
                    b = j;
                    c = squareRootCand;
            }
        }
    }

Then using mathematical property: squareRootCand*squareRootCand = (rem - j)^2 = rem^2 -2*rem*j + j^2 and a few simplifications:

    for (int i=1; 3*i < n; i++) {
        int i2 = i*i;
        int rem = n-i;
        int rem2 = rem*rem;
        for (int j=i+1; 2*j<=rem; j++) {
            if (rem2 - i2 == 2 * rem * j) {
                    a = i;
                    b = j;
                    c = rem - j;
            }
        }
    }

Getting a bit crazy, we can see that we actually want j == (rem2 - i2) / (2*rem) and the division to work fine:

    for (int i=1; 3*i < n; i++) {
        int i2 = i*i;
        int rem = n-i;
        int rem2 = rem*rem;
        int tmp1 = rem2 - i2;
        int tmp2 = 2 * rem;
        if (tmp1 % tmp2 == 0)
        {
            int tmp3 = tmp1 / tmp2;
            for (int j=i+1; 2*j<=rem; j++) {
                if (tmp3 == j) {
                        a = i;
                        b = j;
                        c = rem - j;
                }
            }
        }
    }

and then we do not really need the j loop: the code is now a single loop:

public static int getProductForPythagoreanTriplerOfPerim(int n) 
{ 
    // a + b + c = n 
    // 0 < a < b < c < n 
    // a^2 + b^2 = c^2 
    int a=0, b=0, c=0; 
    for (int i=1; 3*i < n; i++) { 
        int rem = n-i; 
        int tmp1 = rem*rem - i*i; 
        int tmp2 = 2 * rem; 
        if (tmp1 % tmp2 == 0) 
        { 
            int j = tmp1 / tmp2; 
            if (i+1 <= j && 2*j <= rem) { // not needed ? 
                a = i; 
                b = j; 
                c = rem - j; 
            } 
        } 
    } 
    return (c==0) ? -1 : a*b*c; 
}

Or, making the math more explicit and adding a check for odd values of n:

public static int getProductForPythagoreanTriplerOfPerim(int n)
{
    // a + b + c = n  =>  c = n - (a + b)
    // a² + b² = c² becomes:
    // a² + b² = (n - (a + b))² = n² + a² + b² + 2ab - 2n(a+b)
    // 2 b (n - a) = n (n - 2a)
    // we must have n = 2m
    // b = n (n-2a) / (2n -2a) = 2m(2m-2a) / (4m - 2a)
    //   = 2m(m-a) / (2m -a )
    //   = n(m-a) / (n-a)
    int a=0, b=0, c=0;
    if (n % 2 == 0) {
        int m = n/2;
        for (int i=1; 3*i < n; i++) {
            int top = n*(m-i);
            int down = n-i;
            if (top % down == 0)
            {
                a = i;
                b = top/down;
                c = down - b;
            }
        }
    }
    return (c==0) ? -1 : a*b*c;
}

Going further

It may not be relevant for this problem (but it may be if you continue on Project Euler problems): a different algorithm can be found using formulas for generating Pythagoran triples.