Hello! I have to create a function that returns the number of "0" digits at the end of the number n! .
for example, zerof(6)=1 , because 6!=720 and there is only one 0 at the end.
The site I submitted it to says it's not fast enough.How can I improve it? Thank you
Sorry @Helios - I deleted a post (because I was wrong!!).
As @Helios pointed out, actually computing the factorial is going to overflow even a long int very quickly, so this isn't really practicable.
You may (and no, I haven't tried it!) be able to do it by a cumulative count, which saves multiplying and dividing. As you climb from 1 to n you will get:
- one or more extra zeroes for every multiple of 10 (one from 10, 20, ...; two from 100, 200, ... etc.)
- one extra zero every time you pass an odd multiple of 5 (because you must also have passed a number ending in 2).
The second source of these is just (n+5) (integer divided by) (10); that's OK and gives f(6)=1.
The first is a bit more difficult ...
Unique prime factorisation gives extra zero for every extra factor of 2*5.
Many more factors of 2 than 5, so, effectively, an extra zero for every extra factor 5.
So, add one extra zero for multiples of 5, or two extra zeroes for multiples of 5*5, etc.
This can be added up as
n/5 + n/(5*5) + n/(5*5*5) + ... where integer division is assumed.
Here's my take (which gives the same answers as the "official" one, up to at least 100000).