Is Factorial Trailing Zeroes easy or hard?

The problem is rated Medium because the trick is recognizing the relationship between trailing zeroes and factors of 10. Once you realize that 5s determine the count, the implementation becomes very short and efficient.

Factorial Trailing Zeroes Python/Java solution

The core logic is identical across languages: repeatedly divide n by 5 and add the result to a running count until n becomes zero. This produces an O(log n) implementation in Python, Java, C++, C#, or JavaScript with just a few lines of code.

How to solve Factorial Trailing Zeroes in O(n)?

An O(n) style solution iterates through every number from 1 to n and counts how many times each number is divisible by 5. Repeatedly divide each multiple of 5 by 5 and accumulate the count. This approach avoids computing the factorial but is slower than the logarithmic math solution.

What is the best approach for Factorial Trailing Zeroes?

The optimal approach counts how many factors of 5 appear in numbers from 1 to n. Compute n/5 + n/25 + n/125 and continue until the divisor exceeds n. This works because trailing zeroes come from factors of 10, and factorials contain more 2s than 5s. The method runs in O(log n) time and O(1) space.

Is Factorial Trailing Zeroes asked at Google/Amazon/Meta?

Factorial Trailing Zeroes is a common interview question at major tech companies including Google, Amazon, and Meta. It tests mathematical reasoning and the ability to recognize patterns in factorial growth rather than brute-force computation.

What data structure is used in Factorial Trailing Zeroes?

No complex data structure is required. The solution relies purely on mathematical counting of prime factors, specifically powers of 5. Only integer variables are needed to accumulate the result.

What is the time complexity of Factorial Trailing Zeroes?

The optimal counting approach runs in O(log n) time because n is repeatedly divided by powers of 5. Only a few iterations are required even for very large values. Space complexity is O(1) since only a few variables are maintained.

Description Solution Video 7:40

172. Factorial Trailing Zeroes

Medium47.5% acceptance5 companies

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 <= 10⁴

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

Asked at 5 companies

Bloomberg

Google Amazon Microsoft Meta

Topics

Math

7:40

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

172. Factorial Trailing Zeroes

Asked at 5 companies

Topics

Similar problems