Project Euler #1 in Java

java

Solution

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

Problem

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?

Original source

Related problems