"Given a number N, find the numbers below N that are divisible by 3 or 5?" Is there any faster way to solve it without using bruteforce?
I can do it in O(N) time. but can it be more faster?
Use inclusion/exclusion principle.
floor(N / 3) + floor(N / 5) — floor(N / 15)
As you said below N. So N cannot be accounted for. The formula will be
floor((N-1)/3) + floor((N-1)/5) — floor((N-1)/LCM(3,5))
Use inclusion/exclusion principle.
floor(N / 3) + floor(N / 5) — floor(N / 15)
As you said below N. So N cannot be accounted for. The formula will be
floor((N-1)/3) + floor((N-1)/5) — floor((N-1)/LCM(3,5))