Skip to main content
Talentd

Factorial Trailing Zeroes - Solution & Explanation

MediumMath15 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

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 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?

Approach Overview

Problem Overview: Given an integer n, return the number of trailing zeroes in n! (n factorial). Trailing zeroes appear when the factorial result contains factors of 10, which are formed by multiplying 2 × 5.

The key observation: factorials contain far more factors of 2 than 5. That means the number of trailing zeroes is determined entirely by how many times 5 appears in the prime factorization of numbers from 1 to n. This turns the problem into a counting exercise rather than computing the factorial itself.

Approach 1: Iterative Counting (O(n log n) time, O(1) space)

Iterate through every number from 1 to n. For each number, repeatedly divide by 5 while it remains divisible. Every successful division contributes one factor of 5. Accumulate these counts across the entire range. For example, 25 contributes two factors because 25 = 5 × 5, and 125 contributes three.

This approach directly counts how many times 5 appears in the prime factorization of each number. It avoids computing the factorial but still checks every value individually. Time complexity is O(n log n) in the worst case due to repeated division, and space complexity is O(1). It’s useful for understanding the mechanics behind trailing zero formation but not optimal for large inputs.

Approach 2: Counting Factors of 5 (O(log n) time, O(1) space)

Instead of examining every number, count how many multiples of 5, 25, 125, and higher powers exist up to n. Each multiple contributes at least one factor of 5. Numbers divisible by higher powers contribute additional factors. The count can be computed using:

n/5 + n/25 + n/125 + ...

Each division counts how many numbers contribute that many factors of 5. Continue dividing by 5 until the divisor exceeds n. The number of iterations grows logarithmically with base 5, giving O(log n) time complexity and O(1) space.

This technique relies purely on mathematical insight rather than iteration over all values. It appears frequently in math and number theory interview problems where counting prime factors leads to an efficient solution.

Recommended for interviews: The counting factors of 5 method is the expected solution. Interviewers want to see that you recognize trailing zeroes come from 10 = 2 × 5 and that 5 is the limiting factor in factorials. Explaining the iterative counting approach first demonstrates understanding, but deriving the logarithmic counting formula shows stronger algorithmic insight.

Approach 1: Counting Factors of 5

To determine the number of trailing zeroes in a factorial (n!), observe that trailing zeroes are produced by 10s in the factorization of n!. Each 10 is the product of a 2 and a 5. In most factorial numbers, there are more factors of 2 than 5. Therefore, the number of trailing zeroes is determined by the number of times 5 is a factor. We count the number of multiples of 5 in the numbers from 1 to n (because each contributes at least one factor of 5). Then, we count the multiples of 25, 125, 625, etc., as these contribute an extra factor of 5 each time. Continue this counting until the power of 5 exceeds n.

The function trailingZeroes calculates the number of trailing zeroes in the factorial of a given number n. It repeatedly divides n by 5, adding the quotient to count, which represents the number of trailing zeroes.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log5 n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Iterative Counting

In this approach, we directly count the number of trailing zeroes by iterating over all the numbers up to n, checking if each is divisible by 5. If so, we increment a counter to track the factors of 5. This approach isn't as efficient as counting the most significant power of 5 due to potentially higher iteration counts.

This C implementation iterates over numbers from 1 to n. For each number, if it is divisible by 5, it divides it further, counting each division as a factor of 5.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log5 n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Mathematics

The problem is actually asking how many factors of 5 are there in [1,n].

Let's take 130 as an example for analysis:

  1. Divide by 5 for the first time, get 26, indicating that there are 26 numbers containing the factor 5;
  2. Divide by 5 for the second time, get 5, indicating that there are 5 numbers containing the factor 5^2;
  3. Divide by 5 for the third time, get 1, indicating that there is 1 number containing the factor 5^3;
  4. Sum up to get the count of all factors of 5 in [1,n].

The time complexity is O(log n), and the space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Counting Factors of 5

Time Complexity: O(log5 n)
Space Complexity: O(1)

Iterative Counting

Time Complexity: O(n log5 n)
Space Complexity: O(1)

Mathematics—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative CountingO(n log n)O(1)When explaining how factors of 5 appear in numbers from 1..n or demonstrating the concept step by step.
Counting Factors of 5O(log n)O(1)Optimal solution for interviews and large inputs; avoids iterating through all numbers.

Video Solution

Factorial Trailing Zeroes | LeetCode 172 | Coding Interview Tutorial • Terrible Whiteboard • 9,877 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Factorial Trailing Zeroes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Abbreviating the Product of a Range

Next

Maximum Trailing Zeros in a Cornered Path