Project Euler #1 efficiency

I've started solving Project Euler problems. Is the code completely optimized?

Question:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below N.

My solution:

import java.util.LinkedList;
import java.util.Scanner;

public class Solution {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
int testCases = sc.nextInt();
for (int i = 0; i < testCases; i++) {
int input = sc.nextInt();
System.out.println(calculate(input));
}

}

public static boolean isMulThree(int input) {

if (input % 3 == 0)
return true;
else
return false;
}

public static boolean isMulFive(int input) {
int val = input % 10;
if (val == 5 || val == 0)
return true;
else
return false;
}

public static int calculate(int input) {
int sums = 0;
for (int i = 1; i < input; i++) {
if (isMulThree(i) || isMulFive(i)) {

}
}
for (int count : al) {
sums = sums + count;
}
return sums;
}
}


I had a general review primed up for this question, but other answers beat me to those more general aspects.

@TheKittyKat provided a good starting point on the most efficient means of calculating the sum of each sequence, and then subtracting the double-count

Now, the solution @TheKittyKat provides for each sequence, is, for example:

for (int i = 5; i < n; i += 5) {
sum += i;
}


If we were to put this in a function:

public static int sumOfSequence(int value, int limit) {
int sum = 0;
for (int i = value; value < limit; i += value) {
sum += i;
}
return sum;
}


So, having generalized that, we can do:

int total = sumOfSequence(3, N) + sumOfSequence(5, N) - sumOfSequence(15, N);


But, there's a trick, the function:

public static int sumOfSequence(int value, int limit) {
int sum = 0;
for (int i = value; value < limit; i += value) {
sum += i;
}
return sum;
}


can be reduced to a single $O(1)$ operation using the math behind a Arithmetic Progression / sum-of-sequence

This boils down to the fact that the sum of a sequence:

$$1k + 2k + ... + (n-1)k + nk = \tfrac{n(1k + nk)}{2}.$$

The equation:

$$\tfrac{n(1k + nk)}{2}$$

can be rewritten as:

$$\tfrac{kn(1 + n)}{2}$$

Now, either $n$ or $(1 + n)$ is even, and any even number times any other even number, is even, so you can always safely halve it.

Thus, the function can be reduced to:

public static int sumOfSequence(int value, int limit) {
final int count = (limit - 1) / value;
return value * count * ( count + 1) / 2;
}


So, the end result, is:

public static int sumOfSequence(int value, int limit) {
final int count = (limit - 1) / value;
return value * count * ( count + 1) / 2;
}

public static void main(String[] args) {

int limit = 1000;

int sum = -sumOfSequence(15, limit) + sumOfSequence(3, limit) + sumOfSequence(5, limit);
System.out.println(sum);
}

• You don't need to divide by two for each term just do it at the end with a bitwise >> 1 Commented Oct 18, 2014 at 14:30
• @TheKittyKat - you could, but then the method sumOfSequence() would produce the wrong results given its name. Commented Oct 18, 2014 at 14:32
• This question has "efficiency" in its title? Commented Oct 18, 2014 at 14:33
• @TheKittyKat I'd also presume that any answer should be robust and correct as well ;) Anyway, this answer is a fantastic example in favor of thinking about the question before you attempt to solve it. Commented Oct 19, 2014 at 3:34

Naming

Your isMulThree method can be renamed to isMultipleOfThree to make the name clearer. (the same goes for isMulFive). Although these methods are really simple enough to not require any method at all. Just inline the calculation in your code.

for (int i = 1; i < input; i++) {
if (i % 3 == 0 || i % 5 == 0) {
sum += i; // as suggested by @tim
}
}


Braces

It is recommended to always use braces:

if (val == 5 || val == 0) {
return true;
} else {
return false;
}


Although it is even more recommended to implement it as:

return input % 5 == 0;


Algorithm

There is a pure mathematical way of solving this problem, which removes the need for iteration completely. This algorithm is described here and here

if (cond) return true; else return false;

    if (input % 3 == 0)
return true;
else
return false;


can be written as

return input % 3 == 0;


isMulFive

Your isMulFive method is overly complicated.

return input % 5 == 0;


would work just as well. Here, you can also see the similarity to isMulThree. So you can create a more abstract method:

isMultiple(int input, int multipleOf) {
return input % multipleOf == 0;
}


Efficiency

isMulThree and isMulFive are not really needed as they are quite simple methods. If you remove them, you save two function calls on each iteration (which can really add up).

Get rid of the list as it impacts performance by quite a bit and is completely unnecessary. Just add directly in the loop: sums += i;

Misc

• define variables where they are needed: define sums right above the second for loop.
• declare interface implementations by their interface: List<Integer> al = new LinkedList<>();.
• rename al to something more expressive.
• drat. you copied my answer? Commented Oct 18, 2014 at 11:00
• "If you remove them, you save two function calls on each iteration" - I'm pretty sure not. This is a basic exercise in function inlining and pretty sure any JRE - if not the compiler itself - can do that easily. A better reason to not have the methods is that they are not really needed for readability. Commented Oct 18, 2014 at 11:02
• @JanDvorak sounds logical, but when I time it, the variant with the two function calls is ten times as slow as the one with inlined code.
– tim
Commented Oct 18, 2014 at 11:16
• @tim remember to dry-run any code before testing it so that the JIT optimises it fully before you measure its speed. Also, make sure to have enough samples to smooth out any noise in measurement. Commented Oct 18, 2014 at 11:18
• @JanDvorak I used this profiling code, which should be fairly accurate (at least it shouldn't be off my a factor of 10). I also used the netbeans profiler with warmup calls, which produces similar results. Still, my setup might somehow prevent proper optimization. In this case it doesn't really matter, because I don't think that inlining the function yourself hurts redability, so I would just to it.
– tim
Commented Oct 18, 2014 at 11:33

A more efficient algorithm can be found when you look at the mathematics of the problem.

The sum of all multiples of 3 and 5 below n is equal to:

The sum of all multiples of 3 below n plus the sum of all multiples of 5 below n. Subtract the sum of all multiples of 15 below n as they are added twice due to being true for both of above.

Therefore we can separate the program into 3 loops that will do the required math

for (int i = 3; i < n; i += 3) {
sum += i;
}


For adding all multiples of 3

for (int i = 5; i < n; i += 5) {
sum += i;
}


For adding all multiples of 5

for (int i = 15; i < n; i += 15) {
sum -= i;
}


For subtracting all multiples of 15

Using this we iterate over less numbers to find the solution compared to checking each number.

|n    |num for all|num for above solution|
|100  | 100       | 58
|1000 | 1000      | 598
|10000| 10000     | 5998

• I'm not entirely convinced that this will really be faster than a slightly improved variant of the OP's original code (avoiding adding to the list and summing directly). Would be interesting to benchmark this. Commented Oct 18, 2014 at 13:00