Factorial Trailing Zeroes
mediumTime: O(log n)Space: O(1)
Signals to notice
trailing zeros in n!count factors of 10 = 2×5count factors of 5
Brute force first
Compute n! and count — impossible for large n.
The key insight
Count factors of 5: n/5 + n/25 + n/125 + ... O(log n).
What must stay true
Each trailing zero = one factor of 10 = 2×5. Factors of 2 are abundant, so count 5s. Multiples of 25 give extra 5s.
Easy way to go wrong
Only counting n/5 — multiples of 25, 125, etc. contribute additional factors of 5.