LeetCode 172: Factorial Trailing Zeroes Solution in Python Explained

Problem Statement

In LeetCode 172, you’re given an integer n. Your task is to return the number of trailing zeroes in n!, where n! is the product of all positive integers up to n (e.g., 5! = 5 * 4 * 3 * 2 * 1 = 120). Trailing zeroes come from factors of 10 (2 * 5 pairs), and the solution should aim for O(log n) time complexity. This differs from Excel column conversion like LeetCode 171: Excel Sheet Column Number, focusing on mathematical analysis rather than string mapping.

Constraints

• 0 <= n <= 10^4

Example

Let’s see some cases:

Copy codeInput: n = 3
Output: 0
Explanation: 3! = 6, no trailing zeroes.

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

Copy codeInput: n = 10
Output: 2
Explanation: 10! = 3628800, two trailing zeroes.

These examples show we’re counting trailing zeroes in factorials.

Understanding the Problem

How do you solve LeetCode 172: Factorial Trailing Zeroes in Python? Take n = 5. Compute 5! = 5 * 4 * 3 * 2 * 1 = 120, which has 1 trailing zero. For n = 10, 10! = 3628800 has 2 trailing zeroes. Trailing zeroes arise from pairs of 2 and 5 in the prime factorization of n!, and since there are always more 2s than 5s, the number of 5s limits the pairs. Directly computing n! is inefficient for large n due to overflow, so we need a smarter approach, counting factors of 5 in O(log n) time. This isn’t a two-sum task like LeetCode 167: Two Sum II - Input Array Is Sorted; it’s about factorial analysis. We’ll use: 1. Counting Factors of 5: O(log n) time, O(1) space—our best solution. 2. Direct Factorial Calculation: O(n) time, O(1) space—an alternative.

Let’s dive into the best solution.

Best Solution: Counting Factors of 5 Approach

Explanation

Counting Factors of 5 determines trailing zeroes by counting how many times 5 is a factor in n!:

• Each trailing zero requires a pair of 2 and 5.
• In n!, factors of 2 are abundant (from even numbers), so 5s are the limiting factor.
• Count factors of 5 by:
• Count numbers divisible by 5 (n//5).
• Count numbers divisible by 25 (n//25).
• Count numbers divisible by 125 (n//125), and so on, until n//5^k = 0.
• Sum these counts to get total 5s, hence trailing zeroes.

This achieves O(log n) time complexity (log base 5 of n, as we divide by increasing powers of 5), O(1) space, and avoids computing the full factorial, making it highly efficient.

For n = 10:

• 5s from 5: 10//5 = 2 (5, 10).
• 5s from 25: 10//25 = 0.
• Total = 2, return 2.

Step-by-Step Example

Example 1: n = 3

Goal: Return 0.

• Start: count = 0.
• Step 1: n // 5 = 3 // 5 = 0, add 0 to count.
• Step 2: n // 25 = 0 // 25 = 0, stop.
• Finish: count = 0, return 0.

Example 2: n = 5

Goal: Return 1.

• Start: count = 0.
• Step 1: n // 5 = 5 // 5 = 1, count = 1.
• Step 2: n // 25 = 5 // 25 = 0, stop.
• Finish: count = 1, return 1.

Example 3: n = 10

Goal: Return 2.

• Start: count = 0.
• Step 1: n // 5 = 10 // 5 = 2, count = 2.
• Step 2: n // 25 = 10 // 25 = 0, stop.
• Finish: count = 2, return 2.

How the Code Works (Counting Factors of 5) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef trailingZeroes(n: int) -> int:
    # Line 1: Initialize count
    count = 0
    # Total factors of 5 (e.g., 0)

    # Line 2: Count factors of 5, 25, 125, etc.
    while n > 0:
        # Continue until n < 5^k (e.g., n=10)

        # Line 3: Divide by current power of 5
        n //= 5
        # Count multiples of 5^k (e.g., 10//5=2)

        # Line 4: Add to total count
        count += n
        # Add contribution (e.g., count=2)

    # Line 5: Return total trailing zeroes
    return count
    # e.g., 2 for n=10

This detailed breakdown clarifies how counting factors of 5 efficiently computes trailing zeroes.

Alternative: Direct Factorial Calculation Approach

Explanation

Direct Factorial Calculation computes n! and counts trailing zeroes:

• Calculate the factorial by multiplying 1 to n.
• Convert to string and count trailing '0's from the end.

It’s a practical alternative, O(n) time (factorial computation), O(1) space (excluding factorial storage), but impractical for large n due to overflow and inefficiency.

For n = 5:

• 5! = 120, count '0's: 1, return 1.

Step-by-Step Example (Alternative)

For n = 5:

• Step 1: factorial = 5 * 4 * 3 * 2 * 1 = 120.
• Step 2: str(120) → "120", count trailing '0's: 1.
• Finish: Return 1.

How the Code Works (Direct Calculation)

Copy codedef trailingZeroesDirect(n: int) -> int:
    if n == 0:
        return 0
    factorial = 1
    for i in range(1, n + 1):
        factorial *= i
    result = str(factorial)
    count = 0
    for char in result[::-1]:
        if char != '0':
            break
        count += 1
    return count

Complexity

• Counting Factors of 5:
• Time: O(log n) – divisions by powers of 5.
• Space: O(1) – constant space.
• Direct Factorial Calculation:
• Time: O(n) – factorial computation.
• Space: O(1) – constant space (excluding factorial).

Efficiency Notes

Counting Factors of 5 is the best solution with O(log n) time and O(1) space, offering scalability and avoiding overflow—Direct Factorial Calculation uses O(n) time and fails for large n due to integer limits, making it simpler but impractical.

Key Insights

• Factors of 5: Limits trailing zeroes.
• Logarithmic: Efficient counting.
• Direct: Intuitive but limited.

Additional Example

For n = 25:

• Goal: 6.
• Counting: 25//5=5, 25//25=1, 5+1=6, return 6.

Edge Cases

• Zero: 0 → 0.
• Small: 1 → 0.
• Large: 100 → 24.

Both solutions handle these, but direct fails for large n.

Final Thoughts

LeetCode 172: Factorial Trailing Zeroes in Python is a clever mathematical challenge. The Counting Factors of 5 solution excels with its logarithmic efficiency and elegance, while Direct Factorial Calculation offers a basic approach. Want more? Try LeetCode 263: Ugly Number for prime factors or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 172 on LeetCode with 10, aiming for 2—test your skills now!