Factorial Trailing Zeroes

Difficulty: Medium
Topics: Math
Link: https://leetcode.com/problems/factorial-trailing-zeroes/

Problem Description

Given an integer n, return the number of trailing zeroes in n!.

Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.

Example 1:


Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:


Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Example 3:


Input: n = 0
Output: 0

Constraints:

0 <= n <= 104

Follow up: Could you write a solution that works in logarithmic time complexity?

Solution

1. Problem Deconstruction (500+ words)

Rewrite the Problem

Technical Version
Given a non‑negative integer n, compute the exponent of the largest power of 10 that divides n! (the factorial of n). Formally, if n! = 2^a · 5^b · ... in its prime factorization, the number of trailing zeros equals min(a, b). Since a ≥ b for all n ≥ 0, the problem reduces to computing b = v₅(n!), the exponent of 5 in the factorization of n!. Hence, the solution is Z(n) = ∑_{i=1}^{∞} ⌊n / 5^i⌋.
Beginner Version
Multiply all whole numbers from 1 to n. The result (called factorial) may end with some zeros. We want to count how many zeros are at the very end. A zero at the end appears each time the number is multiplied by 10. To get a 10, we need a factor of 2 and a factor of 5. Since there are many more 2’s (every even number contributes at least one 2), the “bottleneck” is the number of 5’s. So we count how many multiples of 5 are in 1 … n, remembering that some numbers (like 25, 125) contain more than one factor of 5.
Mathematical Version
Let n ∈ ℕ₀. Define n! = ∏_{k=1}^n k. The number of trailing zeros Z(n) in the decimal representation of n! satisfies
```
Z(n) = \max\{k ∈ ℕ₀ : 10^k \mid n!\} = \min\{v_2(n!),\, v_5(n!)\},
```
where v_p(m) denotes the exponent of prime p in the factorization of m. Because v_2(n!) ≥ v_5(n!) for all n, we have
```
Z(n) = v_5(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{5^i} \right\rfloor.
```
The sum is finite because terms become zero when 5^i > n.

Constraint Analysis

0 ≤ n ≤ 10⁴
- Limitation on computational approach: A brute‑force computation of n! as an integer would require handling numbers with up to ≈ n log n digits (for n=10⁴, about 35,660 digits), which is infeasible for direct representation in primitive types and extremely inefficient. Hence, an analytic formula is necessary.
- Edge cases implied:
  - n = 0: 0! = 1 by convention, which has no trailing zeros. The formula ⌊0/5⌋ = 0 handles this.
  - n < 5: All terms ⌊n/5^i⌋ are zero, so the result is 0.
  - n is a multiple of a high power of 5 (e.g., 25, 125, …): These values test whether the algorithm correctly counts extra factors. For n = 25, the answer is 6, not 5.
- Upper‑bound on output: For n = 10⁴, the number of trailing zeros is
```
\left\lfloor\frac{10000}{5}\right\rfloor + \left\lfloor\frac{10000}{25}\right\rfloor + \left\lfloor\frac{10000}{125}\right\rfloor + \left\lfloor\frac{10000}{625}\right\rfloor + \left\lfloor\frac{10000}{3125}\right\rfloor = 2000 + 400 + 80 + 16 + 3 = 2499,
```
  which fits comfortably in a 32‑bit integer.

2. Intuition Scaffolding

Generate 3 Analogies

Real‑World Metaphor (Factory Assembly)
Imagine a factory that produces widgets. Each widget requires one bolt (factor 2) and one nut (factor 5). Bolts are plentiful, but nuts are scarce and sometimes come in packs of 5 (like a multiple of 25) that count as two nuts. The number of complete widgets you can assemble equals the total number of nuts, counting each pack appropriately. Similarly, each trailing zero needs a 2‑5 pair; the 2’s are abundant, so the zero count equals the total number of 5’s, with higher multiples contributing extra.
Gaming Analogy (RPG Crafting)
In a role‑playing game, to craft a legendary sword you need “fire essence” (factor 2) and “ice shards” (factor 5). Fire essence drops from every even‑numbered enemy, but ice shards drop only from enemies whose level is a multiple of 5. Some elite enemies (multiples of 25) drop two shards, bosses (multiples of 125) drop three, etc. The number of swords you can craft is the total ice shards collected after clearing all levels 1 through n.
Math Analogy (Minimum of Two Counts)
Given two sequences a_i and b_i, the number of complete pairs (a_i, b_i) is min(∑ a_i, ∑ b_i). In n!, the sequence for 2’s grows faster than for 5’s, so the minimum is always the sum for 5’s. This is akin to a bipartite matching where one side is larger—the matching size equals the size of the smaller side.

Common Pitfalls Section

Counting only single factors of 5 – For n=25, simply counting multiples of 5 gives 5, missing the extra factor from 25.
Computing n! directly – Even with big integers, the computation is prohibitively expensive and unnecessary.
Counting both 2’s and 5’s – While correct, it wastes time because the 2‑count is always larger.
Incorrect loop termination – Using a fixed number of iterations (e.g., up to n) instead of continuing while 5^i ≤ n.
Misinterpreting trailing zeros – Counting all zeros in the number, not just those at the end.
Ignoring that 0! = 1 – Assuming 0! = 0 or having no output.
Floating‑point arithmetic – Using division without floor, leading to rounding errors.

3. Approach Encyclopedia

Approach 1: Brute Force (Compute Factorial)

Pseudocode

def trailingZeroes(n):
    fact = 1
    for i in range(2, n+1):
        fact *= i          # Grows astronomically
    s = str(fact)
    count = 0
    for ch in reversed(s):
        if ch == '0':
            count += 1
        else:
            break
    return count

Complexity Proof
Let D = log₁₀(n!) ≈ n log n digits. Multiplication of two k‑digit numbers takes O(k log k) time with advanced algorithms, but a naive loop does O(k²). Over n multiplications, total time is O(n D²) ≈ O(n³ log² n). Space is O(D) ≈ O(n log n).

Visualization

n=5: fact = 1 → 2 → 6 → 24 → 120
Convert "120" → reverse "021" → count zeros until '1' → 1 zero.

Approach 2: Count Factors per Number

Pseudocode

def trailingZeroes(n):
    total = 0
    for i in range(1, n+1):
        while i % 5 == 0:
            total += 1
            i //= 5
    return total

Complexity Proof
Outer loop runs n times. Inner while loop runs at most log₅ i ≤ log₅ n times. Thus time = O(n log n). Space = O(1).

Visualization

n=10:
i=1:0, i=2:0, i=3:0, i=4:0, i=5:1, i=6:0, i=7:0, i=8:0, i=9:0, i=10:1
total = 2.

Approach 3: Summation of Floors (Optimal)

Pseudocode

def trailingZeroes(n):
    count = 0
    power = 5
    while power <= n:
        count += n // power
        power *= 5
    return count

Complexity Proof
Let k = ⌊log₅ n⌋. The loop runs k times. Each iteration does one integer division and multiplication. Time = O(log n). Space = O(1).

Visualization

n=100:
power=5  → count += 100//5 = 20
power=25 → count += 100//25 = 4
power=125 → 125>100, stop.
total=24.

Approach 4: Repeated Division (Most Elegant)

Pseudocode

def trailingZeroes(n):
    count = 0
    while n:
        n //= 5
        count += n
    return count

Complexity Proof
Each iteration reduces n by a factor of 5, so iterations = ⌊log₅ n⌋ + 1. Time = O(log n). Space = O(1).

Visualization

n=25:
iteration 1: n//5=5, count=5, n=5
iteration 2: n//5=1, count=6, n=1
iteration 3: n//5=0, count=6, n=0 → stop.

4. Code Deep Dive

Optimal Solution (Repeated Division)

def trailingZeroes(n: int) -> int:
    count = 0            # Step 1: Initialize accumulator for total factors of 5
    while n > 0:         # Step 2: Continue while there are still multiples of the current power of 5
        n //= 5          # Step 3: Integer division by 5. 
                         #   First iteration: counts multiples of 5 (⌊n/5⌋).
                         #   Second iteration: n now is ⌊n/5⌋, so n//5 counts multiples of 25 (⌊n/25⌋), etc.
        count += n       # Step 4: Add the quotient to the total.
    return count         # Step 5: Return the accumulated sum, which equals ∑⌊n/5ⁱ⌋.

Edge‑Case Handling

Example 1 (n=3)
Loop condition 3>0 → n//5=0, count=0, loop ends → returns 0.
Example 2 (n=5)
Iteration 1: n//5=1, count=1, n=1.
Iteration 2: n//5=0, count=1, loop ends → returns 1.
Example 3 (n=0)
Loop condition false immediately → returns 0.
Large n (n=10000)
Iteration 1: n//5=2000, count=2000, n=2000.
Iteration 2: n//5=400, count=2400, n=400.
Iteration 3: n//5=80, count=2480, n=80.
Iteration 4: n//5=16, count=2496, n=16.
Iteration 5: n//5=3, count=2499, n=3.
Iteration 6: n//5=0, count=2499, loop ends.

5. Complexity War Room

Hardware‑Aware Analysis

For n ≤ 10⁴, the loop runs at most 6 times (5⁶ = 15625). Each iteration is an integer division and addition, typically 1‑2 CPU cycles. The entire routine fits in L1 cache, with memory footprint of two 64‑bit registers (~16 bytes). Even for the maximum input, execution time is negligible (< 100 ns on modern hardware).

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force (compute n!)	O(n³ log² n) (est.)	O(n log n)	High (straightforward)	❌ Fails beyond tiny n
Per‑number factor counting	O(n log n)	O(1)	Medium	⚠️ Acceptable for small n, not scalable
Summation of floors	O(log n)	O(1)	High	✅ Recommended, clear and optimal
Repeated division	O(log n)	O(1)	Very High	✅ Best: concise, efficient, elegant

6. Pro Mode Extras

Variants Section

Trailing Zeros in Other Bases
For a base b with prime factorization b = ∏ p_i^{e_i}, the number of trailing zeros in n! in base b is
```
Z_b(n) = \min_{i} \left\lfloor \frac{v_{p_i}(n!)}{e_i} \right\rfloor,
```
where v_{p_i}(n!) = ∑_{k≥1} ⌊n / p_i^k⌋.
Example: Base 16 (16=2⁴), Z_{16}(n) = ⌊v₂(n!)/4⌋.
Digits in Factorial
The number of digits of n! in base 10 is ⌊log₁₀(n!)⌋ + 1. Using log₁₀(n!) ≈ n log₁₀ n - n log₁₀ e + O(log n) (Stirling) or summing log₁₀ k from 1 to n.
LeetCode 793 – Preimage Size of Factorial Zeroes Function
Given k, how many non‑negative integers n have exactly k trailing zeros in n!? This involves inverting the function Z(n).
Counting Prime Factors in a Range
Generalize to compute v_p(n!) for any prime p using Legendre’s formula: v_p(n!) = (n - s_p(n))/(p-1) where s_p(n) is the sum of digits of n in base p.

Interview Cheat Sheet

First Statement: “Trailing zeros come from factors of 10, so we need the number of 2‑5 pairs. Since 2’s are abundant, we only count 5’s.”
Formula: Z(n) = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + …
Optimal Algorithm: Repeated integer division by 5 until zero.
Complexity: O(log₅ n) time, O(1) space.
Edge Cases: n=0 (0! = 1), n<5 (result 0), multiples of high powers of 5.
Why Not Count 2’s? Because v₂(n!) ≥ v₅(n!) for all n, so the minimum is always v₅(n!).
Testing: Verify with n=25 (result 6), n=100 (24), n=0 (0).
Follow‑up: If asked about base b, explain prime‑factorization approach.

#172 - Factorial Trailing Zeroes

Factorial Trailing Zeroes

Problem Description

Solution

1. Problem Deconstruction (500+ words)

2. Intuition Scaffolding

3. Approach Encyclopedia

4. Code Deep Dive

5. Complexity War Room

6. Pro Mode Extras