Trailing Zeros of A Factorial With Legendre’s Formula

Legendre’s Formula

There is a theorem in number theory known as Legendre’s Formula. It states that if N is a positive integer and p is a prime number, then the highest power of p that divides N! is given by the following formula

Translating math to english this reads “The highest power of p that divides N! is the infinite sum of the floor of N divided by p to the current exponent”

We know that the infinite sum will eventually reach a terminal value of 0 as at some point, we will reach a large enough exponent for p that the result of dividing n by p raised to i is less than 1. And taking the floor of any value less than 1 will give us 0. Therefore, we do not need to worry about adding up an infinite amount of quotients unless our N is astronomically large.

Adaptation For Trailing Zeros

This formula will allow us to determine the highest power of p in N!. But what about non-prime values? We can take the prime factorization of our target number and run separate instances of the function. Since 10 is the product of 2 and 5, we can simply take the minimum value returned by running the formula on 2, and then 5.

But, knowing that powers of 5 will always be larger than powers of two, the number returned by Legendre’s formula for 5 will always be smaller. Therefore, we can dispense with the minimum function altogether and simply find out how many exponents of 5 divide into the factorial. This will give us the number of trailing zeros.

Example Problems

Trailing zeros in 100!

We have 24 trailing zeros in 100!

Trailing zeros in 95!

We have 22 traling zeros in 95!

Trailing Zeros Coding Question

Suppose we want to write a program to find the number of trailing zeros in n!. We can simply translate our algorithm into code. We will use a while loop to iterate until the floor of our number divided by 5 to our current exponent yields zero. While iterating we will track the sum and return it upon termination. Leetcode features this exact question.

def trailingZeroes(self, n: int) -> int:
    power = 1
    sum = 0
    while (n//(5**power) != 0):
        sum+=(n//(5**power))
        power+=1
    return sum

Originally published at https://www.pranav.ai on June 8, 2021.