Factorial Trailing Zeroes

How it works

Each trailing zero needs a factor pair of two and five. Factorials contain more twos than fives, so count fives. Multiples of 25 contribute an extra five, multiples of 125 another, and repeated division by five counts all these contributions.

Steps

1. Add n // 5.
2. Repeat with n // 5 until it is zero.
3. Return the accumulated contributions.

Complexity

• Time: O(log₅ n).
• Space: O(log₅ n) for the recursive examples.

Things to watch for

• Do not compute n!; it quickly overflows.
• Multiples of 25 contribute twice.
• Zero factorial has zero trailing zeros.

class Solution:
  def trailingZeroes(self, n: int) -> int:
    return 0 if n == 0 else n // 5 + self.trailingZeroes(n // 5)

class Solution {
 public:
  int trailingZeroes(int n) {
    return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
  }
};