Factorial Trailing Zeroes solution and explanation
Google
9 more videos on this problem
Factorial Trailing Zeroes | LeetCode 172 | Coding Interview TutorialTerrible Whiteboard · 7:40 · 9K views
Leetcode 172. Factorial Trailing Zeroes [Java]if else statement · 6:43 · 4K views
LeetCode 172. Factorial Trailing Zeroes PythonTechZoo · 4:00 · 1K views
Factorial trailing zeroes | Coding Interview Problem | LeetcodeHelper Func · 6:01 · 1K views
LeetCode 172: Factorial Trailing Zeroes | Python Solution | Math & Number TheoryCode Scribbler · 5:21 · 850 views
LeetCode 172: Factorial Trailing Zeroes | Java Solution | Math ApproachCode Scribbler · 5:22 · 758 views
172. Factorial Trailing Zeroes | Leetcode | Math based | FundamentalsCoding with Tamilarasan · 4:33 · 683 views
LeetCode 172 | Factorial Trailing Zeroes | Count Number of 5s | JavaSleepy Cracker · 2:17 · 210 views
LeetCode 172: Factorial Trailing Zeroes | C# Solution | Math ApproachCode Scribbler · 5:35 · 127 views
LeetCode Q 172: Factorial Trailing ZeroesSweet AI · 2:07 · 121 views
The problem
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.
def trailingZeroes(n):
count = 0
while n > 0:
n //= 5
count += n
return count
print(trailingZeroes(5))public class FactorialTrailingZeroes {
public int trailingZeroes(int n) {
int count = 0;
while (n > 0) {
n /= 5;
count += n;
}
return count;
}
public static void main(String[] args) {
FactorialTrailingZeroes sol = new FactorialTrailingZeroes();
int n = 5;
System.out.println(sol.trailingZeroes(n));
}
}#include <iostream>
using namespace std;
int trailingZeroes(int n) {
int count = 0;
for (int i = 5; n / i > 0; i *= 5) {
count += n / i;
}
return count;
}
int main() {
int n = 5;
cout << trailingZeroes(n) << endl;
return 0;
}function trailingZeroes(n) {
let count = 0;
while (n > 0) {
n = Math.floor(n / 5);
count += n;
}
return count;
}
console.log(trailingZeroes(5));#include <stdio.h>
int trailingZeroes(int n) {
int count = 0;
while (n > 0) {
n /= 5;
count += n;
}
return count;
}
int main() {
int n = 5;
printf("%d\n", trailingZeroes(n));
return 0;
}using System;
class FactorialTrailingZeroes {
public static int TrailingZeroes(int n) {
int count = 0;
while (n > 0) {
n /= 5;
count += n;
}
return count;
}
static void Main() {
int n = 5;
Console.WriteLine(TrailingZeroes(n));
}
}This Python function iteratively reduces n by dividing it by 5 and incrementing a counter by the result of the division.
Time Complexity: O(log5 n)
Space Complexity: O(1)
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.
def trailingZeroes(n):
count = 0
for i in range(1, n + 1):
num = i
while num % 5 == 0 and num > 0:
count += 1
num //= 5
return count
print(trailingZeroes(5))public class FactorialTrailingZeroesIterative {
public int trailingZeroes(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
int num = i;
while (num % 5 == 0 && num > 0) {
count++;
num /= 5;
}
}
return count;
}
public static void main(String[] args) {
FactorialTrailingZeroesIterative sol = new FactorialTrailingZeroesIterative();
int n = 5;
System.out.println(sol.trailingZeroes(n));
}
}#include <iostream>
using namespace std;
int trailingZeroes(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
int num = i;
while (num % 5 == 0 && num > 0) {
count++;
num /= 5;
}
}
return count;
}
int main() {
int n = 5;
cout << trailingZeroes(n) << endl;
return 0;
}function trailingZeroes(n) {
let count = 0;
for (let i = 1; i <= n; i++) {
let num = i;
while (num % 5 === 0 && num > 0) {
count++;
num /= 5;
}
}
return count;
}
console.log(trailingZeroes(5));#include <stdio.h>
int trailingZeroes(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
int num = i;
while (num % 5 == 0 && num > 0) {
count++;
num /= 5;
}
}
return count;
}
int main() {
int n = 5;
printf("%d\n", trailingZeroes(n));
return 0;
}using System;
class FactorialTrailingZeroesIterative {
public static int TrailingZeroes(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
int num = i;
while (num % 5 == 0 && num > 0) {
count++;
num /= 5;
}
}
return count;
}
static void Main() {
int n = 5;
Console.WriteLine(TrailingZeroes(n));
}
}Python version iteratively determines the number of factors of 5 in the sequence from 1 to n, summing these to find total trailing zeroes.
Time Complexity: O(n log5 n)
Space Complexity: O(1)
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:
- Divide by
5for the first time, get26, indicating that there are26numbers containing the factor5; - Divide by
5for the second time, get5, indicating that there are5numbers containing the factor5^2; - Divide by
5for the third time, get1, indicating that there is1number containing the factor5^3; - Sum up to get the count of all factors of
5in[1,n].
The time complexity is O(log n), and the space complexity is O(1).
function trailingZeroes(n: number): number {
let ans = 0;
while (n > 0) {
n = Math.floor(n / 5);
ans += n;
}
return ans;
}func trailingZeroes(n int) int {
ans := 0
for n > 0 {
n /= 5
ans += n
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Counting Factors of 5 | Time Complexity: O(log5 n) |
| Iterative Counting | Time Complexity: O(n log5 n) |
| Mathematics | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Counting | O(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 5 | O(log n) | O(1) | Optimal solution for interviews and large inputs; avoids iterating through all numbers. |
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.