#172 Factorial Trailing Zeroes
the problem
In plain words
Return how many zeros n! ends with. Bonus: do it in O(log n) time.
in n = 3
out 0
3! = 6.
in n = 5
out 1
5! = 120.
in n = 0
out 0
0! = 1.
- 0 ≤ n ≤ 10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternMath shortcut (closed form)
Each trailing zero is a factor 10 = 2 × 5. Even numbers bring far more 2s than multiples of 5 bring 5s, so count the 5s: n/5 numbers give one, n/25 give a second, n/125 a third, … (Legendre's formula).
solutions
From brute force to optimal
Multiply out n! and count how many times it divides by 10.
- f = 1; multiply by 2..n (BigInteger: 21! already overflows a long).
- While f % 10 == 0: f /= 10, count++.
n! has O(n log n) digits (35,660 for n = 10⁴) and each of the n multiplications walks all of them.
The digits of n!.
class Solution { public int trailingZeroes(int n) { BigInteger f = BigInteger.ONE; // n! outgrows a long at n = 21 for (int i = 2; i <= n; i++) f = f.multiply(BigInteger.valueOf(i)); int zeros = 0; while (f.mod(BigInteger.TEN).signum() == 0) { f = f.divide(BigInteger.TEN); zeros++; } return zeros; }}For each multiple of 5 up to n, count how many times 5 divides it.
- For k = 5, 10, 15, … ≤ n: while k % 5 == 0, count++ and k /= 5.
n/5 multiples; the inner loop runs n/5 + n/25 + … < n/4 times in total.
A counter.
class Solution { public int trailingZeroes(int n) { int fives = 0; for (int k = 5; k <= n; k += 5) { // only multiples of 5 contribute a 5 for (int x = k; x % 5 == 0; x /= 5) fives++; // 25 gives two 5s, 125 gives three } return fives; // 2s are always more plentiful than 5s }}Add n/5 + n/25 + n/125 + … by dividing n by 5 repeatedly.
- zeros = 0.
- While n > 0: n /= 5; zeros += n.
log₅ n divisions — 5 for n = 10⁴.
One counter.
class Solution { public int trailingZeroes(int n) { int zeros = 0; while (n > 0) { n /= 5; // multiples of 5, then of 25, then of 125, ... zeros += n; } return zeros; }}in the room
How to say it in the interview
talk track
- Start from "a zero is a 10 = 2 × 5" and argue that 5s are the bottleneck.
- Show why 25 counts twice, then write the 3-line loop. Dividing n (instead of multiplying a power of 5) also avoids overflow.
traps
- Computing n! in a
long— it overflows at 21!. - Looping
for (p = 5; p <= n; p *= 5)with anintp: for huge n, p * 5 overflows. Dividing n is safer.
what they ask next
Follow-ups
How many x have exactly k trailing zeros in x! (LC 793)?
The count is non-decreasing in x, so binary search on x with this formula. The answer is always 0 or 5.
before you submit
Edge cases to test
- n = 0 → 0 (0! = 1)
- n = 25 → 6, not 5 (25 brings two 5s)
- n < 5 → 0
practise next
Similar problems
- #268Missing NumberEasyin Bits
- #62Unique PathsMediumin Dynamic Programming