LeetCode 172 Factorial Trailing Zeroes (Medium)| Count Trailing Zeroes in Factorials Solution In Java

Trailing Zeroes in Factorial (Java Algorithm)

Counting trailing zeroes in a factorial is a common programming problem asked in coding interviews and competitive exams. The challenge is to compute the result efficiently without calculating large factorial values.

Why Trailing Zeroes Occur in Factorials

Trailing zeroes are created by factors of 10, and a factor of 10 is produced by multiplying 2 × 5.

In factorials, factors of 2 are abundant, but factors of 5 are limited. Therefore, the number of trailing zeroes in n! depends on how many times 5 appears as a factor in numbers from 1 to n.

Example: n = 25

• Multiples of 5: 5, 10, 15, 20, 25
• Each contributes at least one factor of 5
• 25 = 5² contributes an extra factor of 5

Instead of counting manually, we use a mathematical approach to count all factors of 5 efficiently.

Efficient Java Solution

The following Java method calculates the number of trailing zeroes in n! using repeated division by 5.

private static int getTrailingZeros(int n) {

    int count = 0;

    while (n > 0) {
        n /= 5;
        count += n;
    }

    return count;
}

How the Algorithm Works

• Divide n by 5 to count multiples of 5
• Add the quotient to the total count
• Repeat until n becomes 0

This approach automatically accounts for extra factors of 5 in numbers like 25, 125, and so on.

Example Walkthrough: n = 100

100 / 5 = 20 → 20 factors of 5

20 / 5 = 4 → additional factors from 25

Total trailing zeroes = 24

Time and Space Complexity

• Time Complexity: O(log n)
• Space Complexity: O(1)

Conclusion

Counting trailing zeroes in a factorial does not require computing large factorial values. By focusing on factors of 5, this algorithm provides a fast, reliable, and interview-ready solution.

This method is efficient, scalable, and widely accepted in technical interviews and competitive programming.