Hackerrank – Project Euler+ #001 – Multiples of 3 and 5

Hackerrank – Problem description

The problem description – Hackerrank.


There is N defined as the maximum constraint.

We could start from 3 to N and sum all numbers divisible by 3 and 5 (using modulo operation). Unfortunately this is not correct solution, because there are some numbers which are summed 2 times. These numbers are divisible by 15. We have to not sum these numbers (divisible by 15).

This solution is ineffective, too. If the N number would be big, we could reach the time limit for finding a solution.

There is a trick to quickly count all numbers which differ always by same value (3, 5 and 15 in our case).

This equation will help us. We need to have the smallest divisible number and biggest divisible number by d and the number count between them (n).
We calculate the count (n) by dividing max number with d.

For example: if there is N = 20. The biggest number smaller than 20 divisible by 3 is 18. The smallest is 3. Their count is calculated as n = 18/3 = 6.
Summing them

    \[\frac{n(min + max)}{2} = \frac{6 \times (3 + 18)}{2} = 63\]


Same approach holds for numbers divisble by 5 and 15.

The equation to solve the challenge:

    \[Sum = {Sum}_3 + {Sum}_5 - {Sum}_{15}\]

I created solution in:

All solutions are also available on my GitHub profile.


Leave a Reply

Your email address will not be published. Required fields are marked *