Project Euler #1 in Java

Question

Project Euler #1:

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

Here is my solution:

public class MultipleFinder {
    
    private static final int MAX_NUMBER = 1000;
    private static final int[] MULTIPLES = new int[] { 3, 5 };

    public static void main(String[] args) {
        long time = System.nanoTime();
        int sum = 0;
        for(int multiple : MULTIPLES) {
            sum += triangle((MAX_NUMBER - 1) / multiple) * multiple;
        }
        sum -= triangle((MAX_NUMBER - 1) / (MULTIPLES[0] * MULTIPLES[1])) * (MULTIPLES[0] * MULTIPLES[1]);
        System.out.println("Result: " + sum + "\nTime used for calculation in nanoseconds: " + (System.nanoTime() - time));
    }

    private static int triangle(int i) {
        return (i + 1) * i / 2;
    }

}

Output:

Result: 233168
Time used for calculation in nanoseconds: 51764

Questions:

• Is there a way to increase efficiency?
• Is there a way to change the code so that I get the correct solution when I add a multiple?

Answer 1

Discussing performance of methods which are almost entirely in the main method, is sort of pointless. Java performance requires hot-spot compiling, and that does not really happen until methods are run many, many times. The main method is run just once, so is seldom compiled efficiently. Perhaps it's only ever interpreted.

In terms of efficiency, the algorithm you are using is documented as being the best for this puzzle. Essentially there is no better way.

Your subsequent question about how to incorporate additional multiples is complicated....

the way the algorithm works right now, is to calculate the sum of multiple sequences. One sequence is:

3, 6, 9, 12, 15, ...

The second sequence is:

5, 10, 15, 20, .....

The algorithm works by taking the sum of the two sequences, and subtracting the 'double-count', those values that are double-counted because they intersect (like 15, above).

If you have multiple sequences, say, 3, 5, and 7, you will need to sum up all the individual sequences, then subtract the double, and triple counts.

You will need to subtract the intersection with 3*5 (15), as well as 3*7 (21), and also the triple-add 3*5*7 (105)

As you add numbers in to the multiples, you will need to find more of the combinations of parameters that intersect, and need to be subtracted.

Answer 2

Two observations:

Instead of private static final int[] MULTIPLES = new int[] { 3, 5 };

You can omit new int[] and write private static final int[] MULTIPLES = { 3, 5 };

Also, since you're setting the MAX_NUMBER why not simply set it to 999? That way your MAX_NUMBER - 1 lines could just be MAX_NUMBER

As was already answered the code works optimally, performance wise, but becomes exponentially more complex if you want to add multiples, which is why, in those expansive cases, I prefer the intuition of the obvious solution.

Answer 3

The problem is with your algorithm. This can be solved efficiently using an O(1) algorithm. The right approach would be this -

Given a number n, find the number of multiples of 3 less than n (lets call this q3), and the number of multiples of 5 less than n(call this q5). Say, n=10, there are 3 multiples of 3 less than 10 ( 3,6 and 9) and there is 1 multiple of 5 less than 10 (5).

Use the formula for arithmetic progression to calculate the sum all multiples of 3 -> (3*(q3)(q3+1)/2).Same can be done to find the sum of all multiples of 5 -> (5(q3)*(q3+1)/2).

We need to be careful about the numbers which are multiples of both 5 and 3, ie, multiples of 15. Since they get added twice (once as a multiple of 3 and then as a multiple of 5), the sum of the multiples of 15 less than n needs to be subtracted to get the final result.

import java.util.*;

public class Main {

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int T = scanner.nextInt();
    long n;
    for (int i = 0; i < T; i++) {
        n = scanner.nextInt();
        System.out.println(getSumMult(n - 1));

    }
}

    public static long getSumMult(long n){
        long res;
        long q3 = n/3;
        long q5 = n/5;
        long q15 = n/15;
        long s3 = (3*q3*(q3+1))/2;
        long s5 = (5*q5*(q5+1))/2;
        long s15 = (15*q15*(q15+1))/2;
        return s3+s5-s15;
    }
}

Answer 4

A few notes to increase the performance INSIGNIFICANTLY:

• Calculating MULTIPLES[0]*MULTIPLES[1] two times can be avoided by using a variable.
• Using Bitwise operation >>1 to divide the product of i * (i+1).
• Calculating MAX_NUMBER - 1 2 times can be avoided as well.

To make the program generic for multiple multiples, you may have to make manifold changes i.e

• to get pairs, triples, etc => All permutation of lengths 1 to multiples.size().
• Decide when to add or subtract.

Suggestion would be to check the formula for size 3,4,5; Conclude a generic formula instead of if checks for each length and then extend it. Do include if the multiples size is 1 :-)