Factorial Trailing Zeroes

Concept

LeetCode #172.
Problem: Given an integer n, return the number of trailing zeroes in n!. You must write an algorithm that runs in $O(\log n)$ time complexity.

Input: n = 5
Output: 1 (5! = 120. There is one trailing zero).

Input: n = 10
Output: 2 (10! = 3628800. There are two trailing zeroes).

The Mathematical Breakdown

How is a trailing zero created in mathematics?
A zero is exclusively created when a number is multiplied by 10.
What makes a 10? A 10 is exclusively formed by multiplying a prime 2 and a prime 5.

Therefore, if we want to know how many zeroes exist in $100!$, we just need to break every number from $1$ to $100$ down into its prime factors, and count how many (2, 5) pairs exist!

The Trick:
In a factorial sequence (1 * 2 * 3 * 4 * 5 * 6...), there is an absolute massive abundance of 2s. Every single even number provides a 2.
However, 5s are incredibly rare. They only appear every 5 numbers (5, 10, 15...).
Because the 2s are virtually infinite, the total number of (2, 5) pairs will be entirely bottlenecked by the number of 5s!
The number of trailing zeroes is exactly equal to the number of times the factor 5 appears in the sequence!

The Multiplier Trap

Let’s say n = 25.
How many numbers from 1 to 25 are multiples of 5?
25 / 5 = 5.
So there are 5 trailing zeroes, right?
Wrong. 25! has exactly 6 trailing zeroes.

Why? Look closely at the number 25.
$25 = 5 \times 5$.
The number 25 physically provides TWO 5s to our count! The number 125 ($5 \times 5 \times 5$) physically provides THREE 5s.
We cannot just divide by 5. We must divide by 5, then divide by 25, then divide by 125, adding up all the extra bonus 5s hidden deep inside the larger powers!

Implementation

We run a while loop, continuously dividing n by 5, and tallying the results.

// Time Complexity: O(log N) (Specifically, log base 5 of N)
// Space Complexity: O(1)

function trailingZeroes(n: number): number {
    let count = 0;
    
    // As long as our number is large enough to contain at least one 5...
    while (n > 0) {
        
        // How many multiples of 5 exist?
        // Math.floor is critical to drop decimals
        n = Math.floor(n / 5);
        
        // Add them to the count
        count += n;
        
        // By setting n = n / 5, the next loop iteration will naturally
        // calculate n / 25! Then n / 125! It magically peels the layers!
    }

    return count;
}

Let’s trace n = 28:

1. n = floor(28 / 5) = 5. count = 5.
2. Loop again. n = floor(5 / 5) = 1. count = 5 + 1 = 6.
3. Loop again. n = floor(1 / 5) = 0. Loop breaks.
   Final Answer: 6 trailing zeroes. The math is flawless.

Interview Questions

Q: A developer suggests using the BigInt API in JS: let result = 1n; for (let i=1n; i<=n; i++) result *= i; and then counting the zeroes on the string. Is this a valid solution?
A: No. While BigInt will mathematically prevent Integer Overflow, calculating massive Factorials takes $O(N)$ time, and converting a 1000-digit BigInt into a string takes massive $O(D)$ heap memory. The prompt explicitly demands an $O(\log n)$ time complexity with $O(1)$ space. The mathematical Prime Factorization approach is the only acceptable answer.