Trailing Zeros Of A Factorial
Problem
Given a non-negative whole number n, report how many zeros sit at the end of n factorial. The factorial itself is astronomically large for even modest n, so computing it and then counting characters is not an option.
Examples
Input: n = 5
Output: 1
Why: 120 ends in a single zeroInput: n = 30
Output: 7Input: n = 0
Output: 0
Why: edge case, 0! is 1 and has no trailing zeroHints
0 / 3
A trailing zero is what a factor of ten leaves behind, so count factors of ten rather than digits.
Ten is two times five, and the numbers from 1 to n hand out far more twos than fives, so one of the two is always the bottleneck.
Count how many of the values up to n are multiples of five, then how many are multiples of twenty-five, then one hundred and twenty-five, and so on. Each higher power contributes one extra five, and the sum of those counts is the answer.
Solution
Every trailing zero comes from a factor of ten, and ten is a two times a five. Between one and n there are always more even numbers than multiples of five, so the fives run out first and the count of fives is the answer. Multiples of five contribute one each, multiples of twenty-five contribute a second, and so on up the powers, which is exactly what the loop adds up. Time is O(log n) because the power grows fivefold each round, and space is O(1).
def trailing_zeros(n):
zeros, power = 0, 5
while power <= n:
zeros += n // power # every multiple of this power gives one more five
power *= 5 # 5, 25, 125 ... each adds a spare five
return zeros
print(trailing_zeros(5)) # -> 1
print(trailing_zeros(30)) # -> 7
print(trailing_zeros(0)) # -> 0
print(trailing_zeros(100)) # -> 24Stuck on the idea rather than the code? Sieve of Eratosthenes covers it.