Блог пользователя Farnan.PUST

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

Автор Farnan.PUST, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Use inclusion/exclusion principle.

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

→ Ответить