Return the number of trailing zeros in n factorial (n!) without computing the factorial itself, for n up to…

Question

Return the number of trailing zeros in n factorial (n!) without computing the factorial itself, for n up to 10^9. A trailing zero comes from a factor of 10 = 2 * 5, and fives are scarcer than twos, so count the multiplicity of 5 in n! using Legendre's formula: floor(n/5) + floor(n/25) + floor(n/125) + ... Return 0 for n < 0.

Prep Room · Answer

**Intuition** A trailing zero in n! comes from a factor of 10 = 2 * 5. In any factorial there are always more factors of 2 than of 5, so the count of trailing…

Factorial trailing zeros