7
\$\begingroup\$

I have following exercise:

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.

So I wrote below code which finds the sum of all multiples of 3 or 5 below 1000.

Main.java:

package pl.hubot.projecteuler.problem1;

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

How it code works?

I declared sum variable, iterated through i = 1 to i = 999 and if i is multiply of 3 or 5 then I add it to the sum. Finally, I printed out the sum variable.

Questions

  • Is it a efficient method to solve this exercise?
  • How can I simplify code?
  • How can I increase performance of this code?
\$\endgroup\$
  • 1
    \$\begingroup\$ Project Euler allows users to submit their code, so you can read the solutions of other people (once you solve the problem). \$\endgroup\$ – Tyler Durden May 3 '17 at 12:21
  • \$\begingroup\$ Something you might find interesting for such tasks is the IntStream class introduced in Java 8 \$\endgroup\$ – styks May 3 '17 at 12:43
  • 1
    \$\begingroup\$ Many Project Euler problems have mathematical solutions, rather than algorithmic ones. I don't find them good as programming exercises, to be honest. They are more math exercises to me. \$\endgroup\$ – Jörg W Mittag May 3 '17 at 14:58
  • \$\begingroup\$ @JörgWMittag agreed, there are more programming-oriented resources out there; however: PE problems usually are solvable in two ways: You can either use brute force, or you can take a step back and think deeper about the problem and look for smarter ways. If that's not a valuable lesson for programmers as well, I don't know what is \$\endgroup\$ – styks May 3 '17 at 15:38
  • \$\begingroup\$ @styks: You're right. There are other similar sites, where you don't submit the answer, but rather submit the code and they run the code on the server, under a (typically rather strict) time limit, which pretty much forces you towards the mathematical solution. \$\endgroup\$ – Jörg W Mittag May 3 '17 at 17:39
10
\$\begingroup\$

I think it is very concise, well done!

For this small problem this will be fast enough.

Code only

I would only add braces around the if body:

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

For performance, please note that modulo is kind of slow. You could implement two variables that hold multiples of 3 and 5.

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

Math

Better will be to go purely mathemathical:

The formula for the sum of an arithmetic series is:

Sn = (n/2) * (a1 + an)

Sn = the sum of the n terms in the sequence.

a1 = the first term in the sequence.

an = the nth term in the sequence.

We need to determine the number of items 'n' in the sequence. For simplicity I name this occurrences.

This is calculated as dividing the limit - 1 by number. Because the integer division, it is rounded down.

The number an is the last multiple that fits below the limit, which is equal to occurrences * number

Calculate the sum om the series for threes, fives and fifteens. The solution is:

Sum(threes) + Sum(fives) - Sum(fifteens)

In code:

public static int sum( int limit, int number )
{
    int occurrences = (limit-1) / number;
    //Below is a rewrite ( thnx to Olivier Grégoire) of:
    // (int) ( ( occurrences / 2.0 ) * (  occurrences * number + number) );
    return number * occurrences * (occurrences + 1) / 2;
}
public static void main( String[] args )
{
    System.out.println(  sum(1000,3) + sum(1000,5) - sum(1000, 15));
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Why the abuse of parentheses? I would rewrite int occurrences = (limit - 1) / number; return number * occurrences * (occurrences + 1) / 2;. No useless doubles (and subsequent cast), less barely readable parentheses. The priority of operations does all the rest. \$\endgroup\$ – Olivier Grégoire May 3 '17 at 14:13
  • \$\begingroup\$ The occurrences line is surely correct (I edited it), but are you sure about the rounding in the second? \$\endgroup\$ – RobAu May 3 '17 at 14:25
  • \$\begingroup\$ occurrences is either odd or even. occurrences + 1 is the opposite. When you multiply them both, you always have an even number, which you can safely divide by 2 without any rounding at all. \$\endgroup\$ – Olivier Grégoire May 4 '17 at 7:26
  • \$\begingroup\$ Ah and because even * (maybe uneven) number is even too, it will work. Thanks! Will edit it in. \$\endgroup\$ – RobAu May 4 '17 at 7:33
2
\$\begingroup\$

Consider generating multiples of 3 or 5 that way you avoid needing to do % 3 or % 5

Other than that the code is neat and about as simple as you can get really.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.