Project Euler #6 in Java

Question

Project Euler #6:

The sum of the squares of the first ten natural numbers is,

\$1^2+2^2+ ... + 10^2 = 385\$

The square of the sum of the first ten natural numbers is,

\$(1+2+ ... + 10)^2 = 55^2 = 3025\$

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is \$3025 − 385 = 2640\$.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Here is my solution:

public class DifferenceFinder {

    private static final int MAX = 100;

    public static void main(String[] args) {
        long time = System.nanoTime();
        int result = MAX * (MAX + 1) / 2;
        result *= result;
        for(int i = 1; i <= MAX; i++) {
            result -= i * i;
        }
        time = System.nanoTime() - time;
        System.out.println("Result: " + result
                + "\nTime used to calculate in nanoseconds: " + time);
    }

}

It simply does:

$$(1+2+ ... + 100)^2-1^2-2^2- ... -100^2$$

Output:

Result: 25164150
Time used to calculate in nanoseconds: 2231

Questions:

1. Is the simplest solution the most efficient one?
2. Does it smell?

Answer 1

Method extraction.

Even for simple programs, having multiple responsibilities in a method is poor practice.

Consider simple extractions, like:

private static int squareOfSum(int limit) {
    int sum = (limit * (limit + 1)) / 2;
    return sum * sum;
}


public static int sumOfSquares(int limit) {
    int sum = 0;
    for (int i = 1; i <= limit; i++) {
        sum += i * i;
    }
    return sum;
}

Then your main method becomes:

int difference = squareOfSum(100) - sumOfSquares(100);
System.out.printf("Difference is %d\n", difference);

By extracting functions, the logic becomes reusable, and discrete. Much better.

Additionally, it allows you to easily change the logic inside the methods to suite your algorithms, and use better algorithms like vnp suggests (+1 to that answer too).

Timing

Your use of the nanos to time your code is misleading. The performance of the code is heavily related to how often the code runs, and, for this example, any performance measurement is unreliable....

Answer 2

A sum of first \$n\$ numbers is \$\frac{n(n+1)}{2}\$. A sum of squares of first \$n\$ numbers is \$\frac{n(n+1)(2n+1)}{6}\$. A difference in question is \$\frac{n^2(n+1)^2}{4} - \frac{n(n+1)(2n+1)}{6} = \frac{(n-2)(n-1)n(n+1)}{12}\$.

This solution is likely the most efficient.

Answer 3

You can linearize this problem, without losing readability. For example my solution from years back:

    int size = 100;
    long qos = (long) Math.pow(size * (size + 1) / 2, 2);
    long soq = size * (size + 1) * (2 * size + 1) / 6;

    System.out.println(qos - soq);

Where qos and soq are known acronyms for me denoting square of sum and sum of squeares.

---

Note however that my code actually had a potential bug called "Possible Loss of Fraction"

    size * (size + 1) / 2

should be

    size * (size + 1.0) / 2

In this example

• size * (size + 1) would be of type int
• size * (size + 1.0) would be of type double

In java

• int / int you will get int
• double / int you will get double

In Java you mostly deal with discrete mathematics while equations do not, note this fact as you start solving Euler problems. In addition remember to note that type double is an approximation.

---

It is also good to use best tool for the task, for example if you know the result will be

You can compute it with wolfram alpha (mathematica/wolfram language) using:

Limit[(n (n - 2) (n - 1) (n + 1))/12, n -> 100]