Java algorithm - Sum of all multiples of 3 or 5 that are below a number n

Sometimes, use of simple algebra improves performance like anything. Let's explore below problem and its probable solution and observer how performance is increased multiple times by just using the simple algebra.

Problem

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.

If we list all the natural numbers below 20 that are multiples of 3 or 5, we get 3, 5, 6, 9, 10, 12, 15, 18. The sum of these multiples is 78.

Write a JavaScript function that will find the sum of all multiples of 3 or 5 that are below a number N, where N is an input parameter to the function.

Solution

Java Program:

import  java.lang.Math;

public class Main {
  public static long forLoopSum(long n) {
    long startTime = System.currentTimeMillis();
    long startTimeN = System.nanoTime();
    long sum = 0;
    for (n = n-1; n >= 1 ;n--) {
      sum += (n%3==0||n%5==0) ? n : 0;
    }
    long endTime = System.currentTimeMillis();
    long endTimeN = System.nanoTime();
    System.out.println("For Loop Total time: "+ (endTime-startTime) + " milliseconds");
    System.out.println("For Loop Total time: "+ (endTimeN-startTimeN) + " nanoseconds");
    return sum;
  }

  public static long  algebraicSum(double N) {
    long startTime = System.currentTimeMillis();
    long startTimeN = System.nanoTime();
    N = N - 1.0d;
    int threes = (int) Math.floor(N / 3.0d);
    int fives = (int) Math.floor(N / 5.0d);
    int fifteen = (int) Math.floor(N / 15.0d);
    long sum = (3 * threes * (threes + 1) + 5 * fives * (fives + 1) - 15 * fifteen * (fifteen + 1)) / 2;
    long endTime = System.currentTimeMillis(); 
    System.out.println("Math.Floor Total time: "+ (endTime-startTime) + " milliseconds");
    System.out.println("Math.Floor Total time: "+ (endTimeN-startTimeN) + " nonoseconds");
    return sum;
  }

  public static void main(String[] args) {
    System.out.println("Time Taken:");
    long a1 = forLoopSum(45678);
    long a2 = algebraicSum(45678);
    System.out.println("\nOutput:");
    System.out.println("For loop answer: "+a1);
    System.out.println("Math.floor answer: "+a2);
  }
}

Output:

Time Taken:
For Loop Total time: 3 milliseconds
For Loop Total time: 2610055 nanoseconds
Math.Floor Total time: 0 milliseconds
Math.Floor Total time: 250027 nonoseconds

Output:
For loop answer: 486804150
Math.floor answer: 486804150

It shows that algebraicSum performed sum ~11 times faster than the forLoopSum.

Do you enjoy this article? please help spread the word. Your views are valuable.
Post your view

• Twitter
• Facebook
• Google
• Tumblr
• Pinterest