*2K*

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

S=\frac{n\ *\ (a\ +\ l)}{2}

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

Our final answer will be

S_3 + S_5 - S_{15}

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);
}
}
}
```

Code language: Java (java)

A working implementation of the code can be found here.

This problem is also available on HackerRank and Project Euler.