Problem Description

Given an integer n, you need to find how many trailing zeroes are in the factorial of n (written as n!).

A factorial n! is the product of all positive integers from 1 to n. For example:

• 5! = 5 × 4 × 3 × 2 × 1 = 120 (which has 1 trailing zero)
• 10! = 3,628,800 (which has 2 trailing zeroes)

Trailing zeroes are the consecutive zeros at the end of a number. The key insight is that trailing zeroes are created by factors of 10, and since 10 = 2 × 5, we need pairs of 2s and 5s in the prime factorization. Since there are always more factors of 2 than 5 in n!, the number of trailing zeroes is determined by counting the factors of 5.

The solution counts all factors of 5 in the numbers from 1 to n:

• Numbers divisible by 5 contribute one factor of 5 each
• Numbers divisible by 25 (which is 5²) contribute an additional factor of 5
• Numbers divisible by 125 (which is 5³) contribute yet another factor of 5
• And so on...

The algorithm repeatedly divides n by 5 and accumulates the quotients to get the total count of factors of 5, which equals the number of trailing zeroes in n!.

Intuition

To understand where trailing zeroes come from, we need to think about what creates a zero at the end of a number. A trailing zero is produced when we multiply by 10, and 10 = 2 × 5.

So in the factorial n!, every time we have a pair of factors 2 and 5, we get a trailing zero. For example, in 5! = 120, we have factors that include both 2 and 5, creating one trailing zero.

The key observation is that in any factorial, we'll always have more factors of 2 than factors of 5. Why? Because every even number contributes at least one factor of 2, and even numbers appear much more frequently than multiples of 5. Therefore, the limiting factor is always the number of 5s.

Now, how do we count the factors of 5 in n!?

• Every 5th number (5, 10, 15, 20, ...) contributes at least one factor of 5
• Every 25th number (25, 50, 75, ...) contributes an extra factor of 5 (since 25 = 5²)
• Every 125th number contributes yet another factor of 5 (since 125 = 5³)
• And so on...

Taking n = 130 as an example:

• ⌊130/5⌋ = 26 numbers contribute their first factor of 5
• ⌊130/25⌋ = 5 numbers contribute a second factor of 5
• ⌊130/125⌋ = 1 number contributes a third factor of 5
• Total factors of 5: 26 + 5 + 1 = 32

This pattern leads us to the elegant solution: keep dividing n by 5 and sum up all the quotients. Each division tells us how many numbers contribute factors at each power of 5.

Solution Approach

The implementation follows directly from the mathematical insight that we need to count all factors of 5 in [1, n].

The algorithm uses a simple iterative approach:

1. Initialize a counter ans to 0 to store the total count of trailing zeroes.

2. Use a while loop that continues as long as n > 0:

   • Divide n by 5 using integer division: n //= 5
   • Add the result to our answer: ans += n
   • This new value of n represents how many numbers contribute factors at the current power of 5

3. Return the accumulated count.

Let's trace through the algorithm with n = 130:

• First iteration: n = 130 // 5 = 26, ans = 0 + 26 = 26
  • This counts numbers divisible by 5¹
• Second iteration: n = 26 // 5 = 5, ans = 26 + 5 = 31
  • This counts numbers divisible by 5² (like 25, 50, 75, 100, 125)
• Third iteration: n = 5 // 5 = 1, ans = 31 + 1 = 32
  • This counts numbers divisible by 5³ (like 125)
• Fourth iteration: n = 1 // 5 = 0, loop ends
• Return ans = 32

The beauty of this approach is that by repeatedly dividing by 5, we automatically account for all powers of 5. Numbers with multiple factors of 5 get counted multiple times, which is exactly what we want.

Time Complexity: O(log₅ n) since we divide n by 5 in each iteration until it becomes 0. Space Complexity: O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's work through a small example with n = 25 to see how the solution finds trailing zeroes in 25!.

First, let's understand what we're looking for. The number 25! has trailing zeroes because it contains pairs of factors 2 and 5. Since factors of 2 are abundant (every even number contributes at least one), we only need to count factors of 5.

Step-by-step execution:

Starting with n = 25 and ans = 0:

Iteration 1:

• Divide: n = 25 // 5 = 5
• Add to answer: ans = 0 + 5 = 5
• This counts: 5, 10, 15, 20, 25 (five numbers divisible by 5)

Iteration 2:

• Divide: n = 5 // 5 = 1
• Add to answer: ans = 5 + 1 = 6
• This counts the extra factor of 5 in 25 (since 25 = 5²)

Iteration 3:

• Divide: n = 1 // 5 = 0
• Loop terminates (n = 0)

Result: ans = 6

Let's verify this makes sense:

• Numbers contributing one factor of 5: 5, 10, 15, 20 (four numbers)
• Numbers contributing two factors of 5: 25 (one number, since 25 = 5 × 5)
• Total factors of 5: 4 + 2 = 6

Therefore, 25! has 6 trailing zeroes. You can verify: 25! = 15,511,210,043,330,985,984,000,000 which indeed has 6 trailing zeroes.

The algorithm elegantly counts all factors of 5 by repeatedly dividing by 5, automatically accounting for numbers that contain multiple factors of 5.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log n)

The algorithm repeatedly divides n by 5 until n becomes 0. In each iteration, n is reduced by a factor of 5 (n //= 5). The number of iterations required is determined by how many times we can divide n by 5 before reaching 0, which is ⌊log₅(n)⌋ + 1 iterations. Since log₅(n) = log(n)/log(5) and constants are ignored in Big-O notation, the time complexity is O(log n).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space. It maintains two variables (ans for accumulating the result and n for the iteration), regardless of the input size. No additional data structures or recursive calls are used, so the space complexity is constant, O(1).

Common Pitfalls

1. Attempting to Calculate the Factorial First

A common mistake is trying to compute n! first and then count the trailing zeroes. This approach fails for two critical reasons:

Why it's problematic:

• Factorial values grow extremely quickly (e.g., 20! = 2,432,902,008,176,640,000)
• Integer overflow occurs even for relatively small values of n
• Converting to string and counting zeroes is inefficient and unnecessary

Incorrect approach:

def trailingZeroes(self, n: int) -> int:
    # DON'T DO THIS - causes overflow for large n
    factorial = 1
    for i in range(1, n + 1):
        factorial *= i
  
    # Count trailing zeroes
    count = 0
    while factorial % 10 == 0:
        count += 1
        factorial //= 10
    return count

Correct approach: Use the mathematical insight that trailing zeroes come from factors of 5, avoiding factorial calculation entirely.

2. Only Counting Numbers Divisible by 5 Once

Another pitfall is counting each multiple of 5 only once, forgetting that numbers like 25, 125, etc., contribute multiple factors of 5.

Incorrect approach:

def trailingZeroes(self, n: int) -> int:
    # This only counts each multiple of 5 once
    return n // 5  # WRONG - misses higher powers of 5

For n = 130, this would return 26 instead of the correct answer 32, missing the extra factors from 25 (5²), 125 (5³), etc.

Correct approach: The iterative division ensures we count all powers of 5:

• 130 // 5 = 26 (numbers with at least one factor of 5)
• 26 // 5 = 5 (numbers with at least two factors of 5)
• 5 // 5 = 1 (numbers with at least three factors of 5)
• Total: 26 + 5 + 1 = 32

3. Using Recursion Without Considering Stack Limitations

While recursion can solve this problem elegantly, it may cause stack overflow for extremely large values of n in languages with limited stack size.

Potentially problematic recursive approach:

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

While this works correctly and is mathematically equivalent to the iterative solution, the iterative approach is generally preferred for better space efficiency and avoiding potential stack overflow issues.