Watch 10 video solutions for Factorial Trailing Zeroes, a medium level problem involving Math. This walkthrough by Neso Academy has 38,437 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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?
Problem Overview: Given an integer n, return the number of trailing zeroes in n! (n factorial). Trailing zeroes appear when the factorial result contains factors of 10, which are formed by multiplying 2 × 5.
The key observation: factorials contain far more factors of 2 than 5. That means the number of trailing zeroes is determined entirely by how many times 5 appears in the prime factorization of numbers from 1 to n. This turns the problem into a counting exercise rather than computing the factorial itself.
Approach 1: Iterative Counting (O(n log n) time, O(1) space)
Iterate through every number from 1 to n. For each number, repeatedly divide by 5 while it remains divisible. Every successful division contributes one factor of 5. Accumulate these counts across the entire range. For example, 25 contributes two factors because 25 = 5 × 5, and 125 contributes three.
This approach directly counts how many times 5 appears in the prime factorization of each number. It avoids computing the factorial but still checks every value individually. Time complexity is O(n log n) in the worst case due to repeated division, and space complexity is O(1). It’s useful for understanding the mechanics behind trailing zero formation but not optimal for large inputs.
Approach 2: Counting Factors of 5 (O(log n) time, O(1) space)
Instead of examining every number, count how many multiples of 5, 25, 125, and higher powers exist up to n. Each multiple contributes at least one factor of 5. Numbers divisible by higher powers contribute additional factors. The count can be computed using:
n/5 + n/25 + n/125 + ...
Each division counts how many numbers contribute that many factors of 5. Continue dividing by 5 until the divisor exceeds n. The number of iterations grows logarithmically with base 5, giving O(log n) time complexity and O(1) space.
This technique relies purely on mathematical insight rather than iteration over all values. It appears frequently in math and number theory interview problems where counting prime factors leads to an efficient solution.
Recommended for interviews: The counting factors of 5 method is the expected solution. Interviewers want to see that you recognize trailing zeroes come from 10 = 2 × 5 and that 5 is the limiting factor in factorials. Explaining the iterative counting approach first demonstrates understanding, but deriving the logarithmic counting formula shows stronger algorithmic insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Counting | O(n log n) | O(1) | When explaining how factors of 5 appear in numbers from 1..n or demonstrating the concept step by step. |
| Counting Factors of 5 | O(log n) | O(1) | Optimal solution for interviews and large inputs; avoids iterating through all numbers. |