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 ‘N’

Input:N = 100

Output:2318

The most naive approach to solve this problem will be

- Iterate over each number till N
- If the number is divisible by 3 or 5, add it to the sum
- Print the sum

This approach can work well to numbers till **N = 10000**. But can take a lot of time for higher numbers. Thus we apply some trick to make our solution efficient.

We know that multiples of 3 form an AP as

*3, 6, 9, 12, 15, 18…*

Similarly multiples of 5 form an AP as

*5, 10, 15, 20, 25, 30…*

Sum both and we get

*3, 5, 6, 9, 12, 15, 15, 18, 20…*

You’ll notice that *15* is repeated. In fact all the multiples of *15* or * 5 * 3* are repeated

*because it got counted twice once in the series of 3 and again in the series of 5*. Hence we’ll subtract the series of 15.

Now we know that sum of AP is given by

here *n* is the number of terms, *a* is the starting term, and *l* is the last term.

Our final answer will be

Go over the comments in the source code for a better understanding.

import java.util.Scanner; /** * Created by studyalgorithms */ class Problem1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long t = sc.nextLong(); for (long i = 0; i < t; i++) { long n = sc.nextLong(); long a = 0, b = 0, d = 0; // Here a, b and d are the count of numbers divisible by 3, 5 and 15 respectively a = (n - 1) / 3; b = (n - 1) / 5; d = (n - 1) / 15; // To get the sum of all numbers divisible by 3 (sum3) i.e. 3+6+9+-----+3n = 3(1+2+3+---+n) = 3*n(n+1)/2 // Similarly sum of all numbers divisible by 5 (sum5) is 5*n(n+1)/2 // Sum of numbers divisible by 15 (sum15) is 15*n(n+1)/2. long sum3 = 3 * a * (a + 1) / 2; long sum5 = 5 * b * (b + 1) / 2; long sum15 = 15 * d * (d + 1) / 2; long c = sum3 + sum5 - sum15; System.out.println(c); } } }

A working implementation of the code can be found here.

This problem is also available on HackerRank and Project Euler.