8
\$\begingroup\$

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
\$\endgroup\$
3
  • 3
    \$\begingroup\$ Coding problems like this are almost always challenging you to find a more clever solution than the obvious iteration/recursion. That's why they have execution time limits. \$\endgroup\$
    – Barmar
    Jul 29 at 14:47
  • 2
    \$\begingroup\$ This is integer sequence A027868 and you can find a wealth of reading (including two different Python implementations) on its OEIS page. \$\endgroup\$ Jul 29 at 16:14
  • \$\begingroup\$ Skip finding the factorial first, and just find the number of trailing zeroes. The number of trailing zeroes is equal to the number of powers of ten in the factorial, which is equal to the number of the prime factors of ten that appear in the factorial, or rather, whichever of the prime factors is less numerous... \$\endgroup\$ Jul 29 at 22:23
17
\$\begingroup\$
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()
\$\endgroup\$
5
  • 1
    \$\begingroup\$ I express my deep sense of gratitude for writing a detailed answer and explaining it so beautifully. \$\endgroup\$ Jul 28 at 16:26
  • 1
    \$\begingroup\$ Great, except that I think both “infinite set of even numbers” and “infinite set of multiples of 5” are countably infinite and thus technically have the same cardinality :) it seems true, OTOH, that in any given finite set 1..n, the smaller of the two subsets is the multiples of 5 \$\endgroup\$ Jul 28 at 18:36
  • \$\begingroup\$ @D.BenKnoble If n>1. If n=1 then each subset has zero elements. \$\endgroup\$ Jul 28 at 19:01
  • \$\begingroup\$ @D.BenKnoble, you're right, and I saw the smiley too. Just trying to keep the explanation at the right level for the code, rather than mathematically rigorous! \$\endgroup\$ Jul 28 at 19:50
  • \$\begingroup\$ I ran into exactly the inverse problem: I scripted a factorial calculator (using awk | dc) and assumed it was rounding somewhere because of the abundance of trailing zeros. Took me a while to spot the pattern. The corollary, of course, is that the value before the trailing zeros is divisible by the remaining power of two. \$\endgroup\$ Jul 28 at 20:59
3
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
4
  • 5
    \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. Just saying that "it's quicker" - without any explanation about what makes it quicker - doesn't help the asker advance their abilities. \$\endgroup\$ Jul 29 at 16:11
  • \$\begingroup\$ what is this function doing? \$\endgroup\$ Jul 31 at 9:28
  • \$\begingroup\$ I need number of zeros, for input 120, i m getting 28, what is 28? \$\endgroup\$ Jul 31 at 9:29
  • \$\begingroup\$ 28 is the number of trailing zeros in the decimal expansion of 120! (as I just checked using Python math.factorial); is that not what you seek? \$\endgroup\$ Aug 8 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.