categories: Code, Interview Question, leetcode, Medium
source: https://leetcode.com/problems/factorial-trailing-zeroes
topics: Mathematics

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

Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.

Idea

Count number of 5, no need to count 2 because always greater than number of 5

class Solution:
    def trailingZeroes(self, n: int) -> int:
 
        zero_count = 0
        for i in range(5, n + 1, 5):
            current = i
            while current % 5 == 0:
                zero_count += 1
                current //= 5
 
        return zero_count

Optimization

Count number of 5 + number of 25 + number of 125 etc

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