Factorial Trailing Zeroes

Factorial Trailing Zeroes

What is this problem about?

The Factorial Trailing Zeroes interview question asks you to find the number of trailing zeroes in $n!$ (n factorial). For example, $5! = 120$, so there is 1 trailing zero. You need to solve this in logarithmic time complexity, meaning you cannot actually calculate the factorial (which would be astronomically large).

Why is this asked in interviews?

Companies like Microsoft and Meta ask the Factorial Trailing Zeroes coding problem to test your mathematical reasoning and number theory knowledge. It evaluates if you can identify that a trailing zero is produced by the multiplication of $2 imes 5$. Since there are always more 2s than 5s in a factorial, the problem reduces to counting how many factors of 5 exist in all numbers from 1 to $n$.

Algorithmic pattern used

The problem follows a Number Theory / Math pattern. The number of trailing zeroes is exactly $\sum_{k=1}^{\infty} \lfloor \frac{n}{5^k} floor$.

1. Initialize count = 0.
2. While n > 0:
   • Divide n by 5.
   • Add the quotient to count.
   • Repeat with the new n. This effectively counts how many multiples of 5, 25, 125, etc., are in the range $[1, n]$.

Example explanation

$n = 25$

1. $25 / 5 = 5$. There are five multiples of 5 (5, 10, 15, 20, 25). Each provides at least one trailing zero. count = 5.
2. $5 / 5 = 1$. One of those multiples (25) is a multiple of $5^2$ ($5 imes 5$), so it provides an additional factor of 5. count = 5 + 1 = 6.
3. $1 / 5 = 0$. Stop. Result: 6.

Common mistakes candidates make

• O(N) approach: Iterating from 1 to $n$ and checking each number for factors of 5. While correct, it's slower than the O(log N) approach.
• Calculating the factorial: Trying to compute $n!$ will result in integer overflow almost immediately (even 20! exceeds a 64-bit integer).
• Ignoring powers of 5: Only counting multiples of 5 and forgetting that 25, 125, etc., contribute multiple 5s.

Interview preparation tip

Remember Legendre's Formula. It's the general formula for finding the exponent of a prime $p$ in the prime factorization of $n!$. This logic is applicable to many "factor counting" problems.