149. Factorial Trailing Zeroes

A trailing zero comes from a factor of 10 = 2 x 5, and factors of 2 are far more plentiful than factors of 5. So the count of trailing zeroes equals the number of times 5 divides into n! — which is n/5 + n/25 + n/125 + ...

Idea

Each trailing zero needs a factor of 10 = 2 × 5. In n!, factors of 2 vastly outnumber factors of 5, so the number of trailing zeroes is limited by the factors of 5.

Counting factors of 5 in n!: every 5th number contributes one 5 (n/5 of them), every 25th contributes an extra 5 (n/25), every 125th one more (n/125), and so on — Legendre's formula.

Algorithm

1. count = 0.
2. While n >= 5: divide n //= 5 and add the result to count.
3. Return count.

(Each iteration's n is effectively original // 5^k.)

Worked example: n = 100

• 100 // 5 = 20 → count 20.
• 20 // 5 = 4 → count 24.
• 4 // 5 = 0 → stop.

Result: 24 trailing zeroes in 100!.

Complexity

• Time: O(log₅ n).
• Space: O(1).

class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        while (n >= 5) {
            n /= 5;
            count += n;
        }
        return count;
    }
}