Project Euler #1 efficiency

Question

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) {
        LinkedList<Integer> al = new LinkedList<>();
        int sums = 0;
        for (int i = 1; i < input; i++) {
            if (isMulThree(i) || isMulFive(i)) {
                al.add(i);

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

Answer 1

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);
}

Answer 2

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

Answer 3

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.

Answer 4

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