Factorial Trailing Zeroes — Solution in Python, Java & C++
Factorial Trailing Zeroes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on math.
Factorial Trailing Zeroes is a medium coding problem on math, asked in Amazon, Google, Infosys and Bloomberg interviews.
- Difficulty: Medium
- Topics: Math
- Asked at: Amazon, Google, Infosys, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer n, return the number of trailing zeroes in n!.
Note that n! = n × (n - 1) × (n - 2) × … × 2 × 1.
Example 1
Input: n = 3
Output: 0
Explanation: 3! = 6, which ends in no zero.
Example 2
Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.
Example 3
Input: n = 30
Output: 7
Constraints
0 <= n <= 100000
Follow-up: Can you do it in logarithmic time?
Hints for Factorial Trailing Zeroes
Hint 1
A trailing zero comes from a factor of 10 = 2 × 5.
Hint 2
Factors of 2 are far more plentiful than factors of 5, so the answer is just the number of 5s in the factorisation of
n!.Hint 3
Count multiples of 5, then of 25, then of 125, … and add them up: 25 contributes two fives, not one.
How to solve Factorial Trailing Zeroes
Each trailing zero is a factor of 10 = 2 × 5, and factors of 2 are far more plentiful than factors of 5 in n!, so the count of zeros equals the number of times 5 divides n!.
Approach
- Start
count = 0andpower = 5. - While
power <= n, addn // powertocountand multiplypowerby 5. - Return
count.
Why it works
By Legendre's formula the exponent of a prime p in n! is ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + …: the first term counts every multiple of p, the second adds the extra factor each multiple of p² carries, and so on. Since the exponent of 2 always exceeds that of 5, the 5s are the bottleneck.
Complexity
- Time —
O(log₅ n) - Space —
O(1)
Pitfalls
- Counting only multiples of 5 undercounts —
25!has six trailing zeros, not five. - Computing
n!and stripping zeros overflows almost immediately.
Reference solution
Python
def trailingZeroes(n: int) -> int:
count = 0
power = 5
while power <= n:
count += n // power
power *= 5
return countJava
public static int trailingZeroes(int n) {
int count = 0;
for (long power = 5; power <= n; power *= 5) {
count += n / power;
}
return count;
}C++
int trailingZeroes(int n) {
int count = 0;
for (long long power = 5; power <= n; power *= 5) {
count += n / power;
}
return count;
}JavaScript
var trailingZeroes = function(n) {
let count = 0;
for (let power = 5; power <= n; power *= 5) {
count += Math.floor(n / power);
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.