### HackerRank - Project Euler #1 - Multiples of 3 and 5

Project Euler: https://projecteuler.net/problem=1

HackerRank: https://www.hackerrank.com/contests/projecteuler/challenges/euler001/problem

The naive approach would be to traverse through 1 to less than N and sum up any multiple of 3 or 5. That's obviously an $$O(n)$$ algorithm. Your program would get terminated against many of the test cases due to time out. The constraint given in HackerRank that is $$1 \leq N \leq 10^9$$ demands a more efficient algorithm.

Of course, there exists a better algorithm otherwise HackerRank would have set the time limit a higher for this program. So, let's find it out.

The series of sum of all N natural numbers is called triangular number sequence. The closed formula for it is: $\sum_{i=1}^{N} i = \dfrac{N(N+1)}{2}$
You can read the proof of this formula here.

### Sum of multiples of 3 below N:

There are $$[N/3]$$ numbers between 1 and N that are divisible by 3.
$S_{3} = 3+6+9+... \hspace{7em}\\ = 3(3/3+6/3+9/3+...) \hspace{1em}\\ = 3(1+2+3+...) \hspace{4em}\\ = 3( \sum_{i=1}^{N/3} i) \hspace{8em}\\ = 3\dfrac{(N/3)(N/3+1)}{2} \hspace{3em}$

### Similarly,

$S_{5} = 5\dfrac{(N/5)(N/5+1)}{2} \hspace{6em}$
Don't forget that there are common multiples of 3 and 5 like 15, 30, 45 etc. If we add $$S_{3}$$ and $$S_{5}$$ then the common multiples will get summed twice. We need to eliminate those common multiples to fix it.

The common multiples of 3 and 5 is a multiple of their Least Common Multiple.

The LCM of 3 and 5 is 15. Therefore, every common multiple of 3 and 5 is a multiple of 15.

### Sum of all common multiples:

$S_{15} = 15\dfrac{(N/15)(N/15+1)}{2} \hspace{6em}$
$$\therefore$$ Sum of multiples of 3 or 5: $$S=S_{3}+S_{5}-S_{15}$$

My Solution in Java:

Voila! We got a $$O(1)$$ algorithm.

My program passed all the testcases on HackerRank.