Factorial Trailing zeroes

172.Factorial Trailing Zeroes

Math

Problem Statement:

Given an integer n, return the number of trailing zeroes in n! Note that n! = n * (n-1) * (n-2) * ... * 3 * 2 * 1.

Example:

Input:

n = 5

→

Output:

1

5! = 120, which has 1 trailing zero

Algorithm:

1. Count factors of 5 (2s are always abundant)
2. Each 5 contributes one trailing zero
3. Consider powers of 5 (25, 125, etc.)
4. Divide by 5 repeatedly to count all 5s

Complexity:

Time: O(log n) | Space: O(1)

Java Solution:

public int trailingZeroes(int n) {
    int count = 0;
    
    // Count factors of 5 at each power level
    while (n != 0) {
        count += n/5;  // Add contribution of current power of 5
        n /= 5;       // Move to next power of 5
    }
    
    return count;
}

Python Solution:

def trailingZeroes(self, n: int) -> int:
    count = 0
    
    # Count factors of 5 at each power level
    while n:
        count += n // 5  # Add contribution of current power of 5
        n //= 5         # Move to next power of 5
    
    return count

C++ Solution:

int trailingZeroes(int n) {
    int count = 0;
    
    // Count factors of 5 at each power level
    while (n) {
        count += n/5;  // Add contribution of current power of 5
        n /= 5;       // Move to next power of 5
    }
    
    return count;
}