Farnan.PUST's blog

"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?

By Farnan.PUST, history, 9 years ago, In English

I can do it in O(N) time. but can it be more faster?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
9 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Use inclusion/exclusion principle.

→ Reply
»
9 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

floor(N / 3) + floor(N / 5) — floor(N / 15)

→ Reply
»
9 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

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))

→ Reply