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

Read the problem statement here:

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.

References:





Comments