Skip to interview prep
Apexed

293. How many trailing zeros does n! have?

EasySearching & selection

Technical
Show model answer

Each trailing zero comes from a factor 10 = 2 × 5, and factors of 2 are more plentiful, so count the factors of 5: ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + … Each term adds the extra 5s contributed by multiples of higher powers. For n = 100 this is 20 + 4 = 24. The loop runs O(log₅ n) times with O(1) space, and never computes the factorial itself.

How many trailing zeros does n! have — Data structures & algorithms interview question — Apexed