Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Input: n = 10
Output: 2
Explanation: 10! = 3628800, two trailing zeros. (From 5 and 10)

Input: n = 0
Output: 0
Explanation: 0! = 1, no trailing zero.

class Solution:
    def trailingZeroes(self, n: int) -> int:
        # Your code here
        pass

Solution Explanation & Interview Strategy

Approach 1: Brute Force (Calculate Factorial, then Count Zeroes) - Not Recommended

A naive approach would be to first calculate n!, then convert it to a string and count trailing zeroes, or repeatedly divide by 10. However, n! grows extremely fast and will quickly overflow standard integer types for even moderately small n (e.g., 21! is already too large for a 64-bit integer). This approach is generally not feasible or what the interviewer is looking for unless n is very small.

class Solution:
    def trailingZeroes_brute(self, n: int) -> int:
        if n < 0: return 0 # Or raise error, factorial undefined for negative
        if n == 0: return 0 # 0! = 1, no trailing zeros

        factorial = 1
        for i in range(1, n + 1):
            factorial *= i
        
        count = 0
        # This part will fail for large factorials due to precision or conversion limits
        while factorial > 0 and factorial % 10 == 0:
            count += 1
            factorial //= 10
        return count

Approach 2: Counting Factors of 5 (Optimal - Logarithmic Time)

As established, the number of trailing zeros is determined by the number of factors of 5 in the prime factorization of n!. To count these, we sum:

• The number of multiples of 5 up to n (i.e., n // 5). These contribute at least one factor of 5.
• The number of multiples of 25 up to n (i.e., n // 25). These contribute an additional factor of 5 (since 25 = 5 * 5, and one factor was already counted by n // 5).
• The number of multiples of 125 up to n (i.e., n // 125). These contribute yet another factor of 5.
• And so on, for all powers of 5 less than or equal to n.

So, the total count of factors of 5 is (n // 5) + (n // 25) + (n // 125) + ... until the term n // (5k) becomes 0.

 

class Solution:
    def trailingZeroes_optimal(self, n: int) -> int:
        if n < 0:
            return 0 # Or handle as an error

        count_of_fives = 0
        power_of_5 = 5
        while n // power_of_5 >= 1:
            count_of_fives += n // power_of_5
            power_of_5 *= 5 
            
        return count_of_fives

# Alternative compact loop for the optimal solution:
class Solution:
    def trailingZeroes_optimal_v2(self, n: int) -> int:
        count = 0
        while n >= 5:
            n //= 5
            count += n
        return count

# Example Usage:
# sol = Solution()
# print(sol.trailingZeroes_optimal(25))   # Output: 6 (25//5=5, 25//25=1. 5+1=6)
# print(sol.trailingZeroes_optimal_v2(25)) # Output: 6