Effeciency Project Euler #1

Question

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.

Could someone point out if there is something wrong with the code; where I should optimize/modify it?

import java.util.Scanner;
public class SumBelowN {
 private double getSum(int N) {
 int n1 = 3;
 int next_n1 = 3;
 int n2 = 5;
 int next_n2 = 5;
 double sum = 0;
 while (next_n1 < N || next_n2 < N) {
 if (next_n1 == next_n2) {
 sum += next_n1;
 next_n1 += n1;
 next_n2 += n2;
 continue;
 } else if (next_n1 < next_n2) {
 sum += next_n1;
 next_n1 += n1;
 continue;
 } else {
 sum += next_n2;
 next_n2 += n2;
 continue;
 }
 }
 return sum;
 }
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 int i = sc.nextInt();
 // print the sum of all the numbers below 'i'
 // which are divisible by both 3 and 5.
 SumBelowN sumBelowN = new SumBelowN();
 System.out.println("Sum: " + sumBelowN.getSum(i));
 sc.close();
 }
}

• Martin R: Did you see Project Euler #1 efficiency? It is about the same problem and also about Java. It was already pointed out in the answers to that question that the solution can be computed in O(1), i.e. without any loop, which would be the most efficient method.
• yadav_vi: @MartinR I went through the above solution and I can say that it is way better. Thanks for pointing it out. Had I posted this on StackOverflow I would have been downvoted into oblivion.

Answer 1

I'm assuming that you did read about the solution that runs in constant time, but wanted to add your own non-constant solution.

continue

Your continue statements are unnecessary; you can just remove them.

Naming

Your naming violates every standard for Java. Java uses camelCase and doesn't allow names to start with uppercase letters.

It is also generally discouraged to use numbers in names if they can be avoided, which in this case they can: n1 could be called three, and n2 could be five. If you want to stay flexible, use firstMultiple and secondMultiple or something similarly expressive.

Constants

As n1 and n2 are constants, I would declare them as static fields.

Comments

As your solution is not straightforward, I would add a comment or two about how it works.

Efficiency

In case you're interested, here are the results that I get if I compare your solution with the solutions from the other thread (mentioned in the comments):

name per call (mean, ns) per call (median, ns) 95th percentile (ns) total (ms) runs
three loops 280 277 256 0.224 1000000
without function calls 392 392 362 0.3136 1000000
getSum 694 695 641 0.5552 1000000
with function calls 3739 3766 3338 2.9912 1000000

• yadav_vi: Yes, the continue statements are unnecessary. Also, could you post a demo of how to use your Timing class. I tried reading it, but couldn't figure out how to use it.
• tim: @yadav_vi I included an example in my first post of the timing class.