Trailing zeros of 100!
srinivas devaki
mr.eightnoteight at gmail.com
Sat Jan 2 20:46:43 EST 2016
let's put an end to this.
from math import log
# simple one to understand. complexity: O(n*log(n))
def countzeros_va(n):
count = 0
for x in xrange(1, n + 1):
while x % 5 == 0:
count += 1
x //= 5
return count
# better approach. complexity: O(log(n))
def countzeros_vb(n):
count, c5 = 0, 5
while c5 <= n:
count += (n // c5)
c5 *= 5
return count
# this is same as before, its just that while loops irk me
def countzeros_vc(n):
return sum(n // (5**x) for x in range(1, int(log(n, 5) + 3)))
# adding +3 to be sure. never trust approximations.
def run_sample_tests():
precal = {3: 0, 60: 14, 100: 24, 1024: 253, 23456: 5861, 8735373: 2183837}
for x in precal:
assert precal[x] == countzeros_va(x) == countzeros_vb(x) ==
countzeros_vc(x)
if __name__ == '__main__':
run_sample_tests()
Although the code is deterministic, it can be further tested from
http://www.wolframalpha.com/widgets/view.jsp?id=54da27e6e09dc404890a578735b9f7d8
http://www.spoj.com/problems/FCTRL/
On Jan 2, 2016 5:22 PM, <katye2007 at gmail.com> wrote:
>
> Hi, newbie here!
> I'm trying to write a python program to find how many trailing zeros are in 100! (factorial of 100).
> I used factorial from the math module, but my efforts to continue failed. Please help.
>
> Thank you,
> Yehuda
> --
> https://mail.python.org/mailman/listinfo/python-list
On Sun, Jan 3, 2016 at 5:50 AM, Ben Finney <ben+python at benfinney.id.au> wrote:
> Robin Koch <robin.koch at t-online.de> writes:
>
>> Am 02.01.2016 um 22:57 schrieb Chris Angelico:
>> >>> But did you actually test it?
>> >>
>> >> Yes, should work for n >= 1.
>
> By “test it”, Chris of course means test it *by implementing it in a
> program and running that program in Python*.
>
>> >> Why do you ask?
>> >
>> > Your "should work" does not sound good as a response to "actually
>> > test". Normally I would expect the response to be "Yes, and it
>> > worked for me" (maybe with a log of an interactive session).
>>
>> Well, honestly, I trusted my math and didn't thought much about the
>> technical limitations.
>
> That's why it's good to actually test the hypothesis in a real computer
> program, run on the actual computer system you're going to use.
>
> Computers are physical systems, with technical compromises to the
> physical constraints under which they were built.
>
> They are not perfect implementations of our ideal mathematics, and
> testing the mathematics is no guarantee the mathematical assumptions
> will survive your program unscathed.
>
> So, a request “Did you actually test it?” is both a polite reminder to
> do that, and an attempt to get you to do so if you didn't.
>
> If you didn't, then answering “yes” is wasting everyone's time.
>
> --
> \ “As the most participatory form of mass speech yet developed, |
> `\ the Internet deserves the highest protection from governmental |
> _o__) intrusion.” —U.S. District Court Judge Dalzell |
> Ben Finney
>
> --
> https://mail.python.org/mailman/listinfo/python-list
More information about the Python-list
mailing list