Factorial Trailing Zeroes

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

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

For example:

• If n = 3, then the output should be 0 because 3! = 6 which has no trailing zeroes.
• If n = 5, then the output should be 1 because 5! = 120 which has one trailing zero.
• If n = 10, then the output should be 2 because 10! = 3628800 which has two trailing zeroes.

What is the most efficient way to calculate the number of trailing zeroes without actually calculating the factorial? Can you write code with logarithmic time complexity?

Trailing Zeroes in Factorial

This problem asks us to find the number of trailing zeroes in the factorial of a given number n. A naive approach would be to calculate the factorial and then count the trailing zeroes. However, this is not efficient and can lead to overflow issues for larger values of n.

Optimal Solution

The key idea is that trailing zeroes are produced by factors of 5 and 2. Since there are always more factors of 2 than 5, we only need to count the number of factors of 5 in the prime factorization of n!.

To count the number of factors of 5, we can use the following approach:

1. Divide n by 5 and add the quotient to the count.
2. Divide n by 25 (5^2) and add the quotient to the count.
3. Divide n by 125 (5^3) and add the quotient to the count.
4. Continue this process until the quotient becomes 0.

Here's the code implementation in Java:

class Solution {
    /**
     * Given an integer n, return the number of trailing zeroes in n!.
     *
     * Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.
     *
     * @param n the integer
     * @return the number of trailing zeroes in n!
     */
    public int trailingZeroes(int n) {
        int count = 0;
        while (n > 0) {
            n /= 5;
            count += n;
        }
        return count;
    }
}

Here's the code implementation in Python:

class Solution:
    def trailingZeroes(self, n: int) -> int:
        count = 0
        while n > 0:
            n //= 5
            count += n
        return count

Big(O) Run-time Analysis

The time complexity of this solution is O(log₅n) because we are dividing n by powers of 5 in each iteration. The number of iterations is logarithmic with base 5.

Big(O) Space Usage Analysis

The space complexity of this solution is O(1) because we are only using a constant amount of extra space.

Edge Cases

• If n is 0, the number of trailing zeroes is 0.
• If n is a large number, the number of trailing zeroes can be large, but the algorithm will still work correctly.

Here are a few examples:

• n = 3: The number of trailing zeroes is 0.
• n = 5: The number of trailing zeroes is 1.
• n = 10: The number of trailing zeroes is 2.
• n = 25: The number of trailing zeroes is 6 (5 from 5, 10, 15, 20 and 1 from 25 which has two 5s).