Factorial Trailing Zeroes
Problem
n, return how many zeros appear at the
end of n! (n! = 1 × 2 × … × n,
with 0! = 1).n = 3Output0 (3! = 6)n = 5Output1 (5! = 120)n = 0Output00 ≤ n ≤ 104 · Follow-up: solve it in logarithmic time.
Try it yourself
class Solution {
public int trailingZeroes(int n) {
}
}
10 = 2 × 5, and factors of 2
are far more common, so just count factors of 5: multiples of 5 give one,
multiples of 25 one more, multiples of 125 another… i.e.
⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + …Instinct Digits, factors, slopes or distances hide a formula - find the invariant, then guard against overflow, negatives and floating-point error.
Memory hack Mod peels, gcd reduces, squares compare - and long saves the day. Peel digits with %10, reduce slopes with gcd, compare squared distances.
Open the Math & Geometry guide →Approaches
Brute ForceCompute n! with BigInteger
O(n2 log n)Space O(n log n)Multiply out the full factorial as a big integer (it has
O(n log n) digits), then strip zeros by repeatedly dividing by 10 while the
remainder is 0. Each of the n multiplications touches every digit.
public int trailingZeroes(int n) { BigInteger fact = BigInteger.ONE; for (int i = 2; i <= n; i++) fact = fact.multiply(BigInteger.valueOf(i)); int zeros = 0; while (fact.mod(BigInteger.TEN).signum() == 0) { fact = fact.divide(BigInteger.TEN); zeros++; } return zeros; }
Obviously correct, but huge numbers make it slow and memory hungry.
BetterCount Factors of 5 in Every Multiple of 5
O(n log n)Space O(1)Trailing zeros = number of (2, 5) pairs in the prime factorisation, and 2s
always outnumber 5s. So walk the multiples of 5 up to n and add how many
times each one divides by 5 (25 contributes 2, 125 contributes 3, …).
public int trailingZeroes(int n) { int count = 0; for (int i = 5; i <= n; i += 5) { int x = i; while (x % 5 == 0) { // each factor 5 pairs with a spare 2 count++; x /= 5; } } return count; }
No big numbers, but still linear in n — misses the follow-up.
OptimalLegendre's Formula (Divide by 5 Repeatedly)
O(log n)Space O(1)Instead of looking at each number, count per power of 5: there are
⌊n/5⌋ multiples of 5, ⌊n/25⌋ of
25, and so on; each level adds one more factor. Dividing n by 5 in a loop
produces exactly these terms and never overflows.
public int trailingZeroes(int n) { int count = 0; while (n > 0) { n /= 5; // multiples of 5, then of 25, then of 125, ... count += n; } return count; }
Dry runn = 3
- start1000[n, count]
- /520t2020 multiples of 5
- /254t244 multiples of 25
- /125024n=0 → answer 24
Logarithmic, three lines — answers the follow-up.
n /= 5 instead of i *= 5 avoids overflow when
n is near Integer.MAX_VALUE.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Compute n! with BigInteger | O(n2 log n) | O(n log n) |
| Better | Count Factors of 5 in Every Multiple of 5 | O(n log n) | O(1) |
| Optimal | Legendre's Formula (Divide by 5 Repeatedly) | O(log n) | O(1) |
- Computing
n!as along— it overflows at 21!. - Counting only
n/5and forgetting extra 5s from 25, 125, … - Looping
for (p = 5; p <= n; p *= 5)with an int —pcan overflow.
- Explain why 5s, not 2s, are the bottleneck before writing any code.
- Walk through n = 25 (answer 6) to show why higher powers matter.
- Name it: this is Legendre's formula for the exponent of a prime in n!.