LeetCode 172: Factorial Trailing Zeroes

Problem Restatement

We are given a non-negative integer:

We need to return the number of trailing zeroes in:

n!

where:

n! = 1 * 2 * 3 * ... * n

A trailing zero is a zero at the end of the decimal representation.

For example:

has:

trailing zeroes.

The problem asks us to compute the answer without explicitly calculating the factorial. The constraints allow values up to 10^4 on LeetCode, though the mathematical method works for much larger numbers. (leetcode.com)

Input and Output

Item	Meaning
Input	Integer `n`
Output	Number of trailing zeroes in `n!`
Trailing zero	A factor of `10` at the end
Important restriction	Do not compute the factorial directly

Example function shape:

def trailingZeroes(n: int) -> int:
    ...

Examples

Example 1:

n = 3

Compute:

3! = 6

No trailing zeroes.

Return:

Example 2:

n = 5

Compute:

5! = 120

There is one trailing zero.

Return:

Example 3:

n = 10

Compute:

10! = 3628800

There are two trailing zeroes.

Return:

First Thought: Compute the Factorial

One possible idea is:

factorial = 1

for i in range(1, n + 1):
    factorial *= i

Then repeatedly divide by 10.

This works for small numbers, but factorials grow extremely quickly.

For example:

100!

already has a huge number of digits.

The problem expects a mathematical solution.

Key Insight

A trailing zero comes from a factor of:

And:

10 = 2 * 5

So the number of trailing zeroes equals the number of pairs:

(2, 5)

inside the prime factorization of n!.

In factorials, factors of 2 are much more common than factors of 5.

So the limiting factor is the number of 5s.

Therefore:

The number of trailing zeroes equals the total number of factors of 5 inside n!.

Counting Factors of 5

Every multiple of 5 contributes at least one factor of 5.

Examples:

Number	Factors of 5 contributed
`5`	`1`
`10`	`1`
`15`	`1`
`20`	`1`
`25`	`2`
`125`	`3`

Notice:

25 = 5 * 5

contributes two factors of 5.

And:

125 = 5 * 5 * 5

contributes three.

So we must count all powers of 5.

The formula becomes:

n // 5
+ n // 25
+ n // 125
+ ...

until the power exceeds n.

Why the Formula Works

Suppose:

n = 25

Multiples of 5:

5, 10, 15, 20, 25

That gives:

25 // 5 = 5

factors of 5.

But 25 contributes an extra factor:

25 = 5 * 5

So add:

25 // 25 = 1

Total:

5 + 1 = 6

Indeed:

25!

has exactly 6 trailing zeroes.

Algorithm

Initialize:

answer = 0

While n > 0:

Divide n by 5.
Add the quotient to the answer.
Continue with the smaller quotient.

Return the answer.

Walkthrough

Use:

n = 100

First division:

100 // 5 = 20

Add:

answer = 20

Second division:

20 // 5 = 4

Add:

answer = 24

Third division:

4 // 5 = 0

Stop.

Return:

So: