Нули в конце факториала появляются из-за множителей 10, а каждое 10 — это произведение 2 × 5. Поскольку множителей 2 всегда больше, чем множителей 5 в любом факториале, нам нужно только подсчитать, сколько раз 5 встречается как множитель.
Для n! каждое кратное 5 даёт хотя бы один множитель 5, кратные 25 дают ещё один, кратные 125 дают ещё один, и так далее. Мы это учитываем, многократно деля n на степени 5:
n // 5 считает кратные 5n // 25 считает кратные 25n // 125 считает кратные 125def trailing_zeros(n):
count = 0
while n >= 5:
n //= 5
count += n
return count
O(log n) — цикл выполняется по одной итерации на каждую степень 5O(1) — используется только одна переменная-счётчикДля n = 25:
25 // 5 = 5 → добавляем 55 // 5 = 1 → добавляем 16 нулей в конце 25!Количество нулей в конце факториала определяется подсчётом множителей 10, что требует равного подсчёта множителей 2 и множителей 5, поскольку они появляются в одинаковых количествах.
Новый — ещё не проверен сообществом
Вы