Project Euler #1 in Java

Question

I'm having problems with this code. I don't want to look at others, so I'm wondering what's wrong with mine.

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.

public class Multiples {
    public static void main (String [] args) {
        int temp = 0;
        int temp2 = 0; 

        for (int i = 0; i <= 1000; i++) {
            if (i % 3 == 0) {
                temp = temp + i;
            }            
        }

        for (int j = 0; j <= 1000; j++) {
            if (j % 5 == 0) {
                temp2 = temp2 + j;
            }
        }

        System.out.println(temp + temp2);
    }
}

The value I get is 267333, which is wrong. Is my adding wrong? I know algorithmically, this code might not be up to par, but it should work, right?

Answer 1

Solutions

1) O(n):

A small improvement for the other answers (i can start from 3):

public static void main(String[] args) {
    int sum = 0;
    for (int i = 3; i < 1000; i++) {
        if (i % 3 == 0 || i % 5 == 0) {
            sum += i;
        }
    }
    System.out.println(sum);
}

For a bigger input number ( Integer.MAX_VALUE instead of 1000 ) it takes:

• 195 seconds

2) O(n) = O(n/3) + O(n/5) + O(n/15):

This is more efficient and uses your initial approach (remove numbers that were taken twice):

public static void main(String[] args) {
    long sum = 0 ;
    for ( long i = 3 ; i < 1000 ; i+=3 ){
        sum+=i;
    }
    for ( long i = 5 ; i < 1000 ; i+=5 ){
        sum+=i;
    }       
    for ( long i = 15 ; i < 1000 ; i+=15 ){
        sum-=i;
    }
    System.out.println(sum);
}

In the first case we have about n (1000) values for i, in the second case we have only about n/3 + n/5 + n/15 (600) values for i. The second one is also better because there are fewer comparisons ( no if involved ).

For a bigger input number ( Integer.MAX_VALUE instead of 1000 ) it takes:

• 9 seconds

3) O(1):

This solution is based on the following observation:

1 + 2 + ... + n = n*(n+1)/2

public static void main(String[] args) {
    int nr = 1000;
    nr--;
    int x3 = nr/3;
    int x5 = nr/5;
    int x15 = nr/15;
    
    long sum1 = 3*x3*(x3+1); 
    long sum2 = 5*x5*(x5+1);
    long sum3 = 15*x15*(x15+1);
    
    long sum = (sum1+sum2-sum3)/2;
    System.out.println(sum);
}

In this case, even if the input is Integer.MAX_VALUE, the computation is very fast ( less than 1 ms ).