Project Euler #1: Multiples of 3 and 5

Original problem statement

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.

Original link from ProjectEuler.

Generic version

Find the sum of all the multiples of 3 or 5 below a given number N.

Input Format:

First line contains T, the number of test cases. followed by T lines each containing an integer N.

Constraints:

1 ≤ N ≤ 10⁹.

Link to the programming version from Hackerrank.

Analysis

Before reading through this section, I encourage you to think of a possible solution of your own first ~🎀

The simple approach would be to iterate from 1 to N and sum up any multiple of 3 or 5, here’s a bonus simple code in C for it:

Euler 1 C implementation

That’s obviously an O(N) algorithm, can we do better ? Yes! O(1) kind of better.
Let’s start by finding the sum of all multiples of 3 below N:

(1) Triangle number, can also be expressed using the explicit format:

Same way, we define the sum of multiples of 5 below N:

Now, you may think that the Sum of all the multiples of 3 or 5 is S = S₃ + S₅, but that’s wrong, given that:

15, 30, ... and all the common multiples of 3 and 5 will be summed twice. 
This can be be fixed by subtracting those common multiples. So a correct solution would be: S = S₃ + S₅ -(all common multiples of 3 and 5).

The question now is, how to calculate those common multiples?

Any common multiple of A and B is a multiple of the least common multiple

We can get the least common multiple, using the below identity, then we calculate the sum of the duplicate numbers,

The correct solution will be then S = S₃ + S₅ S₁₅

Implementation

  • Using Python
Euler 1 Python implementation

Show your love and support by clicking the clap 👏