Efficient algorithm to calculate the most right non-zero digit of a number's factorial in Python

Question

Calculate the most right non-zero digit of n factorial efficiently

I want to calculate the right most digit of a given number's factorial and print it. What I've done so far is:

import math
n = int(input())
fact = math.factorial(n)
print(str(fact).rstrip('0')[-1])

but I still get time limits and I look for faster solutions. It's worth noting that I must use python to solve this problem.
Also, I shall point out that n is from 1 to 65536, the time limit is 0.5 seconds and I have 256 megabytes of memory.

Answer 1

There is a neat recursive formula you can use: let D(n) be the last non-zero digit in n!

• If n<10, use a lookup table
• If the second last digit of n is odd, D(n) = 4 * D(n//5) * D(unit digit of n)
• If the second last digit of n is even, D(n) = 6 * D(n//5) * D(Unit digit of n)

See this math stackexchange post for a proof.

Translating it into code:

def last_nonzero_factorial_digit(n):
    lookup = [1, 1, 2, 6, 4, 2, 2, 4, 2, 8]
    if n < 10:
        return lookup[n]

    if ((n // 10) % 10) % 2 == 0:
        return (6 * last_nonzero_factorial_digit(n // 5) * lookup[n % 10]) % 10
    else:
        return (4 * last_nonzero_factorial_digit(n // 5) * lookup[n % 10]) % 10

On my laptop, this version runs ~14,000 times faster on a 5-digit number.