Scale Engineer

Factorial Trailing Zeroes

Med
#0172Time: O(n^2 * (log n)^2)Space: O(n log n)1 company
Patterns
Math
Companies
Google

Prompt

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

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

 

Example 1:

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

Example 2:

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

Example 3:

Input: n = 0
Output: 0

 

Constraints:

  • 0 <= n <= 104

 

Follow up: Could you write a solution that works in logarithmic time complexity?

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves first calculating the exact value of n! and then counting the number of trailing zeroes. Since n! grows incredibly fast, standard integer types like int or long will overflow even for small values of n. Therefore, a special class capable of handling arbitrarily large integers, such as BigInteger in Java, is required.

Algorithm

  • Handle the base case: if n is 0, 0! is 1, which has 0 trailing zeroes.
  • Initialize a BigInteger variable, factorial, to BigInteger.ONE.
  • Iterate from 1 to n. In each iteration, multiply factorial by the current number i (converted to a BigInteger).
  • After computing the full factorial, initialize a counter zeroCount to 0.
  • Repeatedly check if the factorial is divisible by 10. As long as it is, increment zeroCount and divide factorial by 10.
  • The final zeroCount is the answer.

Walkthrough

The most straightforward way to solve the problem is to simulate the process directly. First, we compute the value of n!. Then, we count how many times we can divide the result by 10 until it's no longer divisible. This count gives us the number of trailing zeroes.

import java.math.BigInteger; class Solution {    public int trailingZeroes(int n) {        if (n < 0) {            return 0; // Factorial is not defined for negative numbers        }                // Step 1: Calculate n!        BigInteger factorial = BigInteger.ONE;        for (int i = 2; i <= n; i++) {            factorial = factorial.multiply(BigInteger.valueOf(i));        }                // Step 2: Count trailing zeroes        int zeroCount = 0;        BigInteger ten = BigInteger.TEN;        while (factorial.compareTo(BigInteger.ZERO) > 0 && factorial.mod(ten).equals(BigInteger.ZERO)) {            zeroCount++;            factorial = factorial.divide(ten);        }                return zeroCount;    }}

This method is correct but extremely inefficient. The value of n! becomes enormous very quickly, and operations on BigInteger are computationally expensive. For the given constraint n <= 10^4, this approach is not feasible.

Complexity

Time

O(n^2 * (log n)^2)

Space

O(n log n)

Trade-offs

Pros

  • Conceptually simple and easy to understand.

Cons

  • Impractical due to massive time and space requirements.

  • Will result in "Time Limit Exceeded" for the given constraints.

  • Prone to overflow if not using a BigInteger-like structure.

Solutions

class Solution {public  int trailingZeroes(int n) {    int ans = 0;    while (n > 0) {      n /= 5;      ans += n;    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem