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