Factorial Trailing Zeroes
mediumTime: O(log n)Space: O(1)
Recognize the pattern
trailing zeros in n!count factors of 10 = 2×5count factors of 5
Brute force idea
Compute n! and count — impossible for large n.
Better approach
Count factors of 5: n/5 + n/25 + n/125 + ... O(log n).
Key invariant
Each trailing zero = one factor of 10 = 2×5. Factors of 2 are abundant, so count 5s. Multiples of 25 give extra 5s.
Watch out for
Only counting n/5 — multiples of 25, 125, etc. contribute additional factors of 5.