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....

• 200_success: Is the timing really misleading? When something takes ~2 microseconds, is it fair to say that startup costs don't count?
• rolfl: @200_success No, what's misleading is suggesting the code takes 2 microseconds when in another context it may take 0.2 microseconds. In addition, there are other things that are not being timed.... but my main concern is using a measure for the timing that is heavily context-dependent

Answer 2

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

enter image description here

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

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

• Margus: In java 1.0 is same as 1d. Where 1f would result in 1.0, but be of type float (equal value, but not same type).

Answer 3

The sum of the first \$n\$ numbers is \$\frac{n(n+1)}{2}\$. The sum of the squares of the first \$n\$ numbers is \$\frac{n(n+1)(2n+1)}{6}\$. So the difference in the question can be expressed as \$\frac{n^2(n+1)^2}{4} - \frac{n(n+1)(2n+1)}{6} = \frac{(3n+2)(n-1)n(n+1)}{12}\$.

This solution is likely the most efficient.

• TheCoffeeCup: This doesn't seem to work. It gives the result 8165850.
• yadav_vi: @MannyMeng verified using the above Summation formulas and it work with much better timings. Just don't compute the difference with command denominator fraction, use the method suggested in the answer above