The counting zeroes in "100!" problem is actually a common high school level math contest problem. You're supposed to calculate it by hand, not with code. The trick was to notice
- 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)):
Your solution still assumes we can break down the problem according to the fundamental theorem of arithmetic, which is a monoid homomorphism. You simply have added more insight into the problem than I.
The goal of the article is show there's a consistent structural framework of problem solving underneath. I mention briefly that you can improve the solution along your lines.
The idea that let's us prove your algorithm above correct using this theory is that monoid morphisms compose (they form a functor category), and that equivalence relations that respect monoid composition induces monoid morphisms to the quotient classes.
Then we just define the equivalnce relation where two numbers are equal if they have the same number of fives in their prime factorization. The composite monoid morphism yields your algorithm.
I didn't want to overcomplicate the article with this, but I did mention it (it's in the hard-to-parse paragraph at the end of the section)
Comments
The counting zeroes in "100!" problem is actually a common high school level math contest problem. You're supposed to calculate it by hand, not with code. The trick was to notice
- 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)):
Your solution still assumes we can break down the problem according to the fundamental theorem of arithmetic, which is a monoid homomorphism. You simply have added more insight into the problem than I.
The goal of the article is show there's a consistent structural framework of problem solving underneath. I mention briefly that you can improve the solution along your lines.
The idea that let's us prove your algorithm above correct using this theory is that monoid morphisms compose (they form a functor category), and that equivalence relations that respect monoid composition induces monoid morphisms to the quotient classes.
Then we just define the equivalnce relation where two numbers are equal if they have the same number of fives in their prime factorization. The composite monoid morphism yields your algorithm.
I didn't want to overcomplicate the article with this, but I did mention it (it's in the hard-to-parse paragraph at the end of the section)
This comment is the most amazingly "smug"[1] genuinely apologetic comment I've ever read. It's just amazing... and informative!
A heartfelt +1 from me! :)
[1] I don't really mean that in a negative way, but it's like Alan Davies and Stephen Fry on QI, if you know what I mean.
EDIT: I realize that we're not on AGT/BGT or something, but you really should add a footnote about this.
Except in your program you forget to count the number of 2's as well and take the minimum of these two numbers.
Well. I suppose you're only solving n! So you're fine