Find the number of trailing zeros in factorial

Question

I am trying to find the "Number of trailing zeros of N!" (N factorial). In the python code I am trying to find the factorial first and then the number of trailing zeros. However, I am getting "Execution Timed Out" error.

1. Why is this code giving the error? Is there anyway to optimize the code to decrease the execution time?
2. Can this code be shortened in terms of lines of code?

def zeros(n):
    fact=1
    if n==1 or n==0:
        return 1
    elif n<0:
        return 0
    else:
        while n>1:
            fact=n*fact
            n=n-1
        count = 0
        while fact >= 1:
            if fact%10==0:
                count+=1
                fact=fact//10
            else:
                break
    return count

Answer 1

if n==1 or n==0:
    return 1

That looks incorrect. 0! and 1! are both equal to 1, which has no trailing zeros, so we should be returning 0 there. If we had some unit tests, this would be more apparent.

---

We don't need to carry all the trailing zeros with us as we multiply; we can divide by ten whenever we have the opportunity, rather than waiting until the end:

    count = 0
    while n > 1:
        fact *= n
        n -= 1
        while fact % 10 == 0:
            count += 1
            fact = fact // 10

---

However, this only gets us a small gain. The real problem is that we have chosen a very inefficient algorithm. We're multiplying by all the numbers in 2..n, but some mathematical insight helps us find a faster technique.

Observe that each trailing zero means a factor of 10, so we just need the lesser count of 2s or 5s in the prime factors of the factorial (which is the count of all 2s or 5s in all the numbers 1..n). We know there will be more 2s than 5s, since even numbers are much more common than multiples of 5, so we just need a way to count how many fives are in the factorial.

At first glance, that would appear to be n÷5, since every 5th number is a multiple of 5. But we would undercount, because 25, 50, 75, ... all have two 5s in their prime factorisation, and 125, 250, 375, ... have three 5s, and so on.

So a simpler algorithm would be to start with n÷5, then add n÷25, n÷125, n÷625, ... We can do that recursively:

def zeros(n):
    if n < 5:
        return 0
    return n // 5 + zeros(n // 5)

We can (and should) unit-test our function:

def zeros(n):
    """
    Return the number of trailing zeros in factorial(n)
    >>> zeros(0)
    0
    >>> zeros(4)
    0
    >>> zeros(5)
    1
    >>> zeros(24)
    4
    >>> zeros(25)
    6
    >>> zeros(625) - zeros(624)
    4
    """
    if n < 5:
        return 0
    return n // 5 + zeros(n // 5)

if __name__ == '__main__':
    import doctest
    doctest.testmod()

Answer 2

Review

You don't need else after return, but it can be there if it improves readability. Removing the last else will bring the code one level down.

Declare variables right before you use them, you can move fact=1 down to first while statement.

There are math.factorial and divmod functions, you can use them to speed the code up a bit (but I'm sure still not enough).

Better idea

A trailing zero means divisibility by 10, you got it right; but the next step is to realize that \$10=2*5\$, so you need just count the number of factors of 2 and 5 in a factorial, not to calculate the factorial itself. Any factorial have much more even factors then divisible by 5, so we can just count factors of 5. A range from 1 to n (including) will have exactly n//5 factors of 5 (no loop, just one division!), but some of them will be factors of \$25=5*5\$, \$125=5*5*5\$ etc. That, I think, is the most confusing thing in this problem, still easily solved.

Answer 3

Recursion adds overhead, especially in memory but also in time, compared to this purely iterative version:

def zeros(n):
    z = 0
    while n >= 5:
        n = n//5
        z = z+n
    return z