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.