Factorial Trailing Zeroes Solution for TCS NQT
Company: TCS NQT · Difficulty: Easy · Topics: Mathematics, Number Theory
Problem Statement
Given an integer n, return the number of trailing zeroes in n!.
Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.
Examples
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
Explanation: 0! = 1, no trailing zero.
Example 4:
Input: n = 10
Output: 2
Explanation: 10! = 3628800, two trailing zeros.
Example 5:
Input: n = 25
Output: 6
Explanation: 25! = 15511210043330985984000000, six trailing zeros.
Intuition
The key insight is that trailing zeros in a factorial come from pairs of 2 and 5 in the prime factorization. Since there are always more factors of 2 than 5 in factorials, we only need to count the number of factors of 5.
The number of trailing zeros = number of times 5 appears as a factor in n!.
Approach
Approach 1: Count Factors of 5 (Optimal)
1. Count how many numbers from 1 to n are divisible by 5
2. Count how many numbers are divisible by 25 (additional factor of 5)
3. Count how many numbers are divisible by 125 (additional factor of 5)
4. Continue for higher powers of 5
5. Sum all counts
Approach 2: Iterative Division
1. Initialize count = 0
2. While n > 0:
- Add n/5 to count
- Divide n by 5
3. Return count
Approach 3: Logarithmic Approach
1. Calculate log5(n)
2. Sum floor(n/5^i) for i from 1 to log5(n)
Dry Run
Let's trace through Example 4: n = 10
Count Factors of 5:
- Numbers divisible by 5: 5, 10 → count = 2
- Numbers divisible by 25: none → count = 2
- Numbers divisible by 125: none → count = 2
- Total trailing zeros = 2
Verification:
- 10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1
- = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1
- = 2 × 5 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1
- = 2² × 5² × 9 × 8 × 7 × 6 × 4 × 3 × 1
- = 100 × (other factors)
- = 3628800 (ends with 00)
Example 5: n = 25
- Numbers divisible by 5: 5, 10, 15, 20, 25 → count = 5
- Numbers divisible by 25: 25 → count = 5 + 1 = 6
- Numbers divisible by 125: none → count = 6
- Total trailing zeros = 6
Key Insights
1. Prime Factorization: Trailing zeros come from 2×5 pairs
2. 2 vs 5: There are always more factors of 2 than 5
3. Power of 5: Each power of 5 contributes an additional factor
4. Efficiency: Don't need to calculate the actual factorial
Edge Cases
1. n = 0: 0! = 1, no trailing zeros
2. n = 1: 1! = 1, no trailing zeros
3. n < 5: No factors of 5, no trailing zeros
4. Large n: Handle overflow carefully
Time and Space Complexity
- Time Complexity: O(log n) - we divide by 5 each time
- Space Complexity: O(1) - constant extra space