Project Euler #1 in Java

Project Euler #1 in Java

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 by Maroun Maroun for Project Euler #1 in Java

You should do:

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

This will add each number only one time. In your code, you will add 15 twice, since it'll be satisfied in both conditions in both loops.

Also note that according to the requirements, you should loop to < 1000, not <=.

Answer by Mureinik for Project Euler #1 in Java

If a number is a multiplier of both 3 and 5 (e.g.: 15, 30, 45, etc.), you will count it twice. So instead of two for loops, you should have one, with a complex condition:

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

Answer by failed.down for Project Euler #1 in Java

You added all multiples of 15 twice. Using your algorithm, run a third loop and test if the number is divisible by 15, then remove it from the total sum.

Answer by user3457026 for Project Euler #1 in Java

Your code is incorrect because of a simple issue: there are numbers which can be divided by 3 and 5 as well. In your code, you count them twice: once in the first loop, and secondly in the second loop. What you should do, is one of the options below:

A. Just run one loop and use two conditions instead of one: check if the number can be divided by 3 and also can be divided by 5 - then, and just then, add it to the total sum.

B. I made a Python code, using the same method as you used, but with an added condition. It's absolutely not recommended and not efficient, but it may help you to understand better.

numlist = []    for i in range (1, 1000):      if i % 3 == 0:          numlist.append(i)      for j in range (1, 1000):      if j % 5 == 0:          if not j in numlist:              numlist.append(j)      counter = 0  for a in numlist:      counter += a      print counter  

Answer by ChrisOdney for Project Euler #1 in Java

public static int sumOfMultiples(int i, int j, int limit){      int s = --limit / i, t = limit / j, u = limit / (i * j);      return (i*(s*(s+1)/2)) + (j*(t*(t+1)/2)) - ((i*j)*(u*(u+1)/2));  }  

Test

actual = Prob1.sumOfMultiples(3, 5, 1000);  assertEquals(233168, actual);  

Answer by engineer for Project Euler #1 in Java

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

Fatal error: Call to a member function getElementsByTagName() on a non-object in D:\XAMPP INSTALLASTION\xampp\htdocs\endunpratama9i\www-stackoverflow-info-proses.php on line 72