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.
Key Insights
- Trailing zeroes in a factorial are produced by the factors of 10 in the product.
- Each factor of 10 is made up of a factor of 2 and a factor of 5.
- In the factorial sequence, there are typically more factors of 2 than factors of 5.
- Therefore, the number of trailing zeroes is determined by the number of times 5 is a factor in the numbers from 1 to n.
- To count the factors of 5, we can use the formula: n // 5 + n // 25 + n // 125 + ... until n // 5^k is 0.
Space and Time Complexity
Time Complexity: O(log n)
Space Complexity: O(1)
Solution
To solve the problem, we will leverage the observation that trailing zeroes are produced by pairs of factors of 2 and 5 in the factorial product. Since there are usually more factors of 2 than 5, we only need to count the factors of 5. We will iteratively divide n by powers of 5 and sum the quotients until n becomes zero. This approach is efficient and operates in logarithmic time complexity relative to n.