Factorial Trailing Zeroes

Math

MediumLeetCode #172

15 min

Problem Statement

Given an integer n, return the number of trailing zeroes in n!.

Example

Example 1:

Input: n = 5

5! has 1 trailing zeroes.

Output: 1

Explanation: 5! = 120, which has one trailing zero.

Solution (Counting Factors of 5)

The number of trailing zeroes in n! is determined by the number of times 10 is a factor in its prime factorization. Since 10 = 2 * 5, and there will always be more factors of 2 than 5, we only need to count the factors of 5.

Algorithm Steps

Initialize a count variable to 0.
While n is greater than 0, do the following:
Divide n by 5.
Add the result to count.
This process counts the numbers divisible by 5, 25, 125, etc., effectively counting all factors of 5.
Return the final count.

Input (n):

Current n

Zeroes Count

Start with n = 25. Trailing zeroes are determined by the number of factors of 5.

Factorial Trailing Zeroes Solution


class Solution:
    def trailingZeroes(self, n: int) -> int:
        count = 0
        while n > 0:
            n //= 5
            count += n
        return count