Search code examples
pythonalgorithmperformanceprimesfactorial

Efficiently count trailing zeros of numbers from a factorial

I am trying to calculate the number of trailing zeroes in a factorial with python per this problem. Thus far, my solution looks like this:

import math
def zeros(n):
    return len(str(math.factorial(n))) - len(str(math.factorial(n)).rstrip('0'))

This works on smaller numbers, but one of the tests is 1000000000!, and the inefficiency of my algorithm causes the system to break.

I have struggled with making algorithm efficiency in the past, and would appreciate any general advice on this subject, as well as any specific pointers to what could make this algorithm more efficient.

Solution

  • Rather than evaluating the factorial computing the length directly, it would be best to use algebraic properties.

    For example, rather than accumulating the total, track the number of multiples of two and five.