DSA problem
Factorial Trailing Zeroes
Given an integer n, return the number of trailing zeroes in n! (n factorial). A trailing zero is a zero at the end of the decimal representation of the number, and n! is defined as 1 * 2 * 3 * ... * n.
A naive approach would compute n! and then count zeros, but n! grows astronomically — 13! already overflows a signed 32-bit integer and 21! overflows 64-bit. We need to count zeros directly from n without ever materializing the factorial.
Every trailing zero in a decimal number corresponds to a factor of ten in its prime factorization, and ten = 2 * 5. Among the integers from 1 to n, factors of two are far more abundant than factors of five (every even number contributes at least one 2, but only every fifth number contributes a 5). So the number of trailing zeros equals the number of times 5 appears in the prime factorization of n!.
Legendre's formula counts exactly that: the exponent of prime p in n! is floor(n / p) + floor(n / p^2) + floor(n / p^3) + ... until the divisor exceeds n. For p = 5 this becomes n / 5 + n / 25 + n / 125 + .... Each term is computed in O(1), and the loop terminates after at most log_5(n) iterations, giving an O(log n) algorithm with O(1) space.
Examples
n = 30n = 51n = 256Constraints
- 0 <= n <= 10^4
- Follow-up: solve the problem in logarithmic time.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.