- number of trailing zeros is equal to times you can divide something by 10
- There are a lot more 2s than 5s as the divisor, so number of 5s is the limiting factor
- 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100 contribute (at least) a factor of 5 each
- 25, 50, 75, 100 contribute another factor of 5 each
So answer is 20 + 4 zeros.
I love monoids but I personally thought that was a bad example. Not only did it complicate the problem, it didn't actually lead to any understanding that will let you write a generic and efficient solution for "n!". Something like this O(log(n)):
def countZeroes(n):
count = 0
divisor = 5
while divisor <= n:
count += n / divisor
divisor *= 5
return count
print countZeroes(100)