Calculate the number of trailing zeros in n! [duplicate]

Write a function which takes n as a parameter, and returns the number of trailing zeros in n!.

0 <= n <= 10^100

Output Constraints

Should be return the result in less than 10 seconds.

Test Input

1
213
45678
1234567
78943533
4567894123
121233112233112231233112323123

Test Output

0
51
11416
308638
19735878
1141973522
30308278058278057808278080759

Shortest code by character count wins.

• I'm not sure if we should have this here, as it's basically the same as spoj.pl/SHORTEN/problems/FACTZERO
– Nabb
Feb 8 '11 at 15:29
• @Nabb, I had no idea that this question was on SPOJ. I've put a significantly larger limit on the input here though. Feb 8 '11 at 15:35
• @Dogbert: The limit is larger but the algorithms here are going to be exactly the same as over at SPOJ.
– Nabb
Feb 8 '11 at 16:03
• for shortest code, you should use the code-golf tag Feb 8 '11 at 19:54
• It's on Euler as well :) (i think) Feb 9 '11 at 5:50

Python 50 47 Characters

n=input()
x=5
s=0
while n/x:s+=n/x;x*=5
print s

Python, 36 Chars

f=lambda n:n//5+(n//5>0and f(n//5)or 0) #Py3k #39 Chars
f=lambda n:n/5+(n/5>0and f(n/5)or 0) #Before 3.0 #36 Chars
• But you still need the input and output right? Mar 8 '11 at 23:59
• @Debanjan, the question states, write a function.... Mar 9 '11 at 5:35
• @sOle:My bad!I missed that. Mar 9 '11 at 6:05

J, 26

! f=:3 :'+/<.y%5^(1+i.144x)'

eg

f 121233112233112231233112323123x
30308278058278057808278080759
f 4567894123
1141973522
f 0
0
f 10^100x
2499999999999999...99999999999999999982

in less than a second for all input examples

f i=length$filter(\x->xmod5/=0)[1..i];main=interact$show.f.read