LeetCode 172 - Factorial Trailing Zeroes

LeetCode Problem 172

Difficulty: 🟡 Medium
Topics: Math

Solution

Problem Understanding

The problem asks us to determine how many trailing zeroes appear at the end of n!, where n! represents the factorial of n.

A factorial is defined as:

$$n! = n \times (n - 1) \times (n - 2) \times \dots \times 2 \times 1$$

For example:

• 5! = 5 × 4 × 3 × 2 × 1 = 120
• 120 ends with one zero, so the answer is 1

A trailing zero is created whenever a number is divisible by 10. Since:

$$10 = 2 \times 5$$

every trailing zero in a factorial comes from a pair of factors (2, 5).

The input is a single integer n, and the output should be the number of trailing zeroes in n!.

The constraints are:

• 0 <= n <= 10^4

Even though the input size is not extremely large, the follow up explicitly asks for a logarithmic time solution. That means we should avoid directly computing the factorial because factorial values grow extremely quickly and become unnecessarily large.

Several edge cases are important:

• n = 0, because 0! = 1, which has no trailing zeroes
• Small values like 1, 2, 3, and 4, which also produce zero trailing zeroes
• Numbers containing multiple factors of 5, such as 25 or 125, because they contribute more than one trailing zero
• Large values where directly computing the factorial could become inefficient or overflow in languages with fixed integer sizes

Approaches

Brute Force Approach

A straightforward solution is to compute the factorial directly and then count how many zeroes appear at the end of the resulting number.

For example:

$$10! = 3628800$$

We could repeatedly divide by 10 while the number ends in 0.

This approach works because trailing zeroes are literally the number of consecutive zero digits at the end of the factorial value.

However, this method is inefficient for several reasons:

• Factorials grow extremely quickly
• The resulting number becomes very large
• Computing the entire factorial is unnecessary because we only care about the count of trailing zeroes
• In many languages, integer overflow becomes a problem for large factorials

Although Python supports arbitrary precision integers, the follow up specifically asks for a logarithmic solution, so brute force is not acceptable.

Optimal Mathematical Observation

The key insight is that trailing zeroes come from factors of 10, and every 10 is formed by one 2 and one 5.

In factorials, factors of 2 are extremely common because every even number contributes at least one 2.

Factors of 5 are much less common, so the number of trailing zeroes is determined entirely by how many times 5 appears in the prime factorization of n!.

We therefore count:

• How many multiples of 5 exist
• How many multiples of 25 exist, because each contributes an extra 5
• How many multiples of 125 exist, because each contributes yet another 5
• And so on

The formula becomes:

$$\left\lfloor \frac{n}{5} \right\rfloor + \left\lfloor \frac{n}{25} \right\rfloor + \left\lfloor \frac{n}{125} \right\rfloor + \dots$$

This produces a very efficient logarithmic solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n) or worse	O(n)	Computes the full factorial and counts ending zeroes
Optimal	O(log₅ n)	O(1)	Counts factors of 5 directly without computing factorial

Algorithm Walkthrough

Optimal Algorithm

1. Initialize a variable called zeroes to 0.

This variable will store the total number of trailing zeroes. 2. Repeatedly divide n by 5.

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

For example:

• 5
• 10
• 15
• 20

all contribute one factor of 5. 3. Add n // 5 to the result.

This counts how many numbers between 1 and n contribute at least one factor of 5. 4. Continue dividing by higher powers of 5.

Some numbers contribute more than one factor of 5.

For example:

• 25 = 5 × 5
• 125 = 5 × 5 × 5

So we must also add:

• n // 25
• n // 125
• and so on

5. Stop when the divisor becomes larger than n.

At that point, no additional multiples exist. 6. Return the accumulated result.

Why it works

Every trailing zero comes from one pair of (2, 5). Since factorials contain far more factors of 2 than factors of 5, the number of trailing zeroes is exactly equal to the number of factors of 5.

The algorithm counts every occurrence of factor 5 in the factorial decomposition. Multiples of 5 contribute one factor, multiples of 25 contribute an extra factor, multiples of 125 contribute another extra factor, and so forth. Therefore, the final count exactly matches the number of trailing zeroes.

Python Solution

class Solution:
    def trailingZeroes(self, n: int) -> int:
        zeroes = 0
        divisor = 5

        while divisor <= n:
            zeroes += n // divisor
            divisor *= 5

        return zeroes

The implementation starts by initializing the result variable zeroes to 0.

The variable divisor begins at 5 because we are counting factors of 5.

Inside the loop:

• n // divisor counts how many numbers contribute that power of 5
• The result is added to zeroes
• The divisor is multiplied by 5 to move to the next power

For example:

• 5
• 25
• 125

The loop terminates once the divisor exceeds n, because no further multiples can contribute factors of 5.

Finally, the total number of trailing zeroes is returned.

Go Solution

func trailingZeroes(n int) int {
    zeroes := 0
    divisor := 5

    for divisor <= n {
        zeroes += n / divisor
        divisor *= 5
    }

    return zeroes
}

The Go implementation follows the exact same logic as the Python solution.

One important difference is that Go uses fixed-width integers, unlike Python's arbitrary precision integers. However, under the given constraints, integer overflow is not a concern because n <= 10^4.

Integer division in Go uses / for integers, which automatically truncates toward zero, matching the behavior needed for this algorithm.

Worked Examples

Example 1

Input:

n = 3

Since 3! = 6, there are no trailing zeroes.

Algorithm trace:

Step	Divisor	n // Divisor	Zeroes
Start	5	-	0

The loop never executes because 5 > 3.

Final answer:

0

Example 2

Input:

n = 5

Since:

$$5! = 120$$

there is one trailing zero.

Algorithm trace:

Step	Divisor	n // Divisor	Zeroes
Start	5	-	0
1	5	1	1

Next divisor becomes 25, which exceeds 5.

Final answer:

1

Example 3

Input:

n = 0

Since:

$$0! = 1$$

there are no trailing zeroes.

Algorithm trace:

Step	Divisor	n // Divisor	Zeroes
Start	5	-	0

The loop never executes.

Final answer:

0

Additional Example: n = 25

This example demonstrates why higher powers of 5 matter.

Algorithm trace:

Step	Divisor	n // Divisor	Zeroes
Start	5	-	0
1	5	5	5
2	25	1	6

Explanation:

• Multiples of 5 contribute five factors of 5
• 25 contributes one extra factor because 25 = 5²

Final answer:

6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log₅ n)	The divisor increases by powers of 5 each iteration
Space	O(1)	Only a few integer variables are used

The loop executes once for each power of 5 less than or equal to n.

For example:

$$5, 25, 125, 625, \dots$$

Because the divisor grows exponentially, the number of iterations is logarithmic in base 5.

The algorithm uses constant extra memory because it stores only a few integer variables regardless of input size.

Test Cases

solution = Solution()

assert solution.trailingZeroes(0) == 0      # 0! = 1
assert solution.trailingZeroes(1) == 0      # no factors of 5
assert solution.trailingZeroes(3) == 0      # example case
assert solution.trailingZeroes(4) == 0      # still no factor of 5
assert solution.trailingZeroes(5) == 1      # first trailing zero
assert solution.trailingZeroes(10) == 2     # 10! ends with two zeroes
assert solution.trailingZeroes(15) == 3     # multiples of 5
assert solution.trailingZeroes(20) == 4     # additional multiples of 5
assert solution.trailingZeroes(25) == 6     # extra factor from 25
assert solution.trailingZeroes(50) == 12    # multiple higher powers of 5
assert solution.trailingZeroes(100) == 24   # standard benchmark case
assert solution.trailingZeroes(125) == 31   # extra factors from 125
assert solution.trailingZeroes(1000) == 249 # large input stress test

Test	Why
n = 0	Validates factorial base case
n = 1	Smallest positive input
n = 3	Example with no trailing zeroes
n = 4	Confirms absence of factor 5
n = 5	First number producing a trailing zero
n = 10	Multiple factors of 5
n = 15	Several multiples of 5
n = 20	More accumulated factors
n = 25	Validates extra factor from 5²
n = 50	Tests repeated power contributions
n = 100	Common benchmark input
n = 125	Validates extra factor from 5³
n = 1000	Large stress test

Edge Cases

Edge Case 1: n = 0

This case is important because many implementations incorrectly assume factorials start at 1!.

However:

$$0! = 1$$

and 1 has no trailing zeroes.

The implementation handles this naturally because the loop condition divisor <= n fails immediately when n = 0, so the function correctly returns 0.

Edge Case 2: Numbers Smaller Than 5

Values such as 1, 2, 3, and 4 contain no factors of 5, so their factorials cannot contain trailing zeroes.

A naive implementation might accidentally perform unnecessary calculations or produce incorrect results if it does not properly handle small inputs.

The algorithm works correctly because the loop never executes for these values.

Edge Case 3: Powers of 5

Numbers like 25, 125, and 625 are easy sources of bugs because they contribute multiple factors of 5.

For example:

$$25 = 5 \times 5$$

If an implementation only counts multiples of 5, it would incorrectly return 5 instead of 6 for 25!.

The algorithm avoids this issue by repeatedly dividing by increasing powers of 5:

$$n // 5,\ n // 25,\ n // 125$$

This ensures every factor of 5 is counted exactly once.

Edge Case 4: Large Inputs

Directly computing factorials for large inputs can become extremely inefficient and may overflow fixed-width integer types in some languages.

The mathematical counting approach avoids constructing the factorial entirely. It uses only division and addition, making it both efficient and safe even for much larger values than the given constraints.