Count the fives
Count the zeros at the end of n! without computing it. About 8 minutes.
A zero is a 2 × 5
Why does 10! = 3,628,800 end in two zeros? Each trailing zero is a factor of 10 hiding in the product, and 10 is 2 times 5. In 1 × 2 × … × n there are plenty of 2s but far fewer 5s, so the 5s are the bottleneck.
Counting trailing zeros means counting how many 5s sit inside all the factors.
- fives
- 1
Each zero at the end needs one 2 × 5. There are plenty of 2s, so count the 5s. 5 gives one.
Some numbers give more than one five
Every multiple of 5 brings one 5: 5, 10, 15, 20. But 25 is 5 times 5, so it brings two, and 125 brings three.
A neat way to count them all: divide n by 5 and add the result, divide that by 5 and add again, and keep going until it reaches 0. For 25 that is 5 + 1 = 6 zeros.
zeros = 0
while n > 0:
n //= 5
zeros += n
return zerosHow many trailing zeros does 25! have?
- A6
- B5
- C2
Show the answer
6. 25 // 5 = 5 multiples of 5, plus 25 // 25 = 1 extra five from 25.
Zeros at the end of n!
Return how many zeros n! = 1 × 2 × … × n ends with (0! = 1).
n = 25 → 6
0 ≤ n ≤ 2,000,000,000