Нули в конце 100!
На собеседовании спросили: сколько нулей в конце числа 100!, и как это аккуратно посчитать без вычисления самого факториала?
Ответить самому
Сначала сформулируйте ответ как на собеседовании, затем откройте разбор и оцените себя.
Короткий ответ
Нули появляются от множителей 10 = 2 * 5. Двоек в 100! больше, поэтому считаем пятерки: floor(100/5) + floor(100/25) = 20 + 4 = 24.
Полный разбор
В конце десятичной записи появляется ноль каждый раз, когда в факториале есть пара множителей 2 и 5. В факториале двоек всегда больше, потому что каждое второе число дает множитель 2, а пятерки встречаются реже. Поэтому задача сводится к подсчету всех множителей 5.
Для 100! числа, кратные 5, дают 20 пятерок: 5, 10, ..., 100. Но числа, кратные 25, дают дополнительную пятерку: 25, 50, 75, 100. Значит, ответ:
Обобщение для n!: складываем floor(n / 5), floor(n / 25), floor(n / 125) и так далее, пока степень 5 не превысит n.
Теория
Это устная number-theory задача: нужно увидеть, что ограничивающий множитель для десяток — это количество пятерок в разложении факториала.
Типичные ошибки
- Считать только 100 / 10 и получить 10.
- Посчитать только числа, кратные 5, и забыть дополнительные пятерки в 25, 50, 75, 100.
- Пытаться вычислять сам факториал.
Как отвечать на собеседовании
- Сначала скажи, что ноль — это пара 2 и 5, а двоек больше.
- Для 100! обязательно отдельно добавь кратные 25.