CODEWITHSUNDEEP
java
priya
priya

Reputation: 129

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?

Upvotes: 6

Views: 13719

Answers (8)

Riya
Riya

Reputation: 1

just write this simple java code.

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

You will get the output as 233168

Upvotes: 0

Aditya Chandeliya
Aditya Chandeliya

Reputation: 1

Some certain conditions occurs where both conditions satisfies for 3 as well as 5 also. like when i=15 satisfies for both 15%3==0 and 15%5==0. so probably your answer is more than expected because you tried for both 3 and 5 separately. by doing this during these certain conditions you add repeated values. Hence it is better to check in single loop. like this -

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

Upvotes: 0

ROMANIA_engineer
ROMANIA_engineer

Reputation: 56666

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

Upvotes: 17

ChrisOdney
ChrisOdney

Reputation: 6384

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

Upvotes: -1

user3457026
user3457026

Reputation: 81

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

Upvotes: 0

michael
michael

Reputation: 667

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.

Upvotes: 0

Mureinik
Mureinik

Reputation: 311498

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

Upvotes: 1

Maroun
Maroun

Reputation: 95968

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

Upvotes: 7

Related Questions