172. Factorial Trailing Zeroes

Time: O(log n)

Space: O(log n)

Intuition

Trailing zeros come from factors of 10 = 2*5. There are always more factors of 2 than 5 in n!, so count only factors of 5. Every multiple of 5 contributes one 5; every multiple of 25 contributes an extra; every multiple of 125 another, etc.

Algorithm

1count = 0.
2While n >= 5: n /= 5. count += n.
3Return count.

Example Walkthrough

Input: n = 25

1.25/5=5 -> count=5. 5/5=1 -> count=6. 1/5=0 -> stop.

Output: 6

Common Pitfalls

•Do not count factors of 2 - they always exceed factors of 5 in n!.

172.cs

// Approach: Trailing zeros come from factors of 10 = 2 x 5, and factors of 2 are always more plentiful.
// So count how many times 5 divides n! by summing n/5 + n/25 + n/125 + ...
// Each term counts multiples of 5, 25, 125, ... contributing extra 5s beyond what was already counted.
// The recursion n/5 + TrailingZeroes(n/5) achieves this cleanly in O(log n) steps.
// Time: O(log n) Space: O(log n) for recursion stack; easily made iterative for O(1) space.

public class Solution
{
    public int TrailingZeroes(int n)
    {
        return n == 0 ? 0 : n / 5 + TrailingZeroes(n / 5);
    }
}

Was this solution helpful?