Factorial Trailing Zeroes
MedPrompt
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
nis 0,0!is 1, which has 0 trailing zeroes. - Initialize a
BigIntegervariable,factorial, toBigInteger.ONE. - Iterate from 1 to
n. In each iteration, multiplyfactorialby the current numberi(converted to aBigInteger). - After computing the full factorial, initialize a counter
zeroCountto 0. - Repeatedly check if the
factorialis divisible by 10. As long as it is, incrementzeroCountand dividefactorialby 10. - The final
zeroCountis 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.
A better approach is to realize that trailing zeroes are formed by factors of 10, which are pairs of 2 and 5. Since factors of 2 are always more abundant than factors of 5 in a factorial's prime factorization, the number of trailing zeroes is determined solely by the number of factors of 5. This approach iterates through all numbers from 1 to n and counts the total number of factors of 5.
Algorithm
- Initialize a counter
zeroCountto 0. - Iterate through all numbers
ifrom 5 ton. We can step by 5 since only multiples of 5 can contribute a factor of 5. - For each number
i, we need to find out how many factors of 5 it contains. For example, 5 has one, 10 has one, but 25 has two. - Create a temporary variable
currentNum = i. - While
currentNumis greater than 0 and is divisible by 5, incrementzeroCountand dividecurrentNumby 5. - After the loop finishes,
zeroCountwill hold the total number of factors of 5 inn!, which is the answer.
Walkthrough
Instead of computing the massive n! value, we can analyze its prime factors. A trailing zero is created by a factor of 10, which is a product of 2 and 5. In the prime factorization of n!, the number of factors of 2 will always be greater than the number of factors of 5. Therefore, the number of trailing zeroes is limited by the count of factors of 5. We can iterate from 1 to n and for each number, count how many factors of 5 it contributes.
class Solution { public int trailingZeroes(int n) { int zeroCount = 0; // We only need to check multiples of 5. for (int i = 5; i <= n; i += 5) { int currentNum = i; // Count factors of 5 in the current number. // e.g., 25 has two factors of 5, 125 has three. while (currentNum > 0 && currentNum % 5 == 0) { zeroCount++; currentNum /= 5; } } return zeroCount; }}This approach avoids the overflow issue and is significantly faster than the brute-force method. It's efficient enough to pass for the given constraints but can still be optimized.
Complexity
Time
O(n log n)
Space
O(1)
Trade-offs
Pros
Avoids calculating the large factorial value, thus preventing overflow.
Much more efficient than the brute-force approach.
Cons
Not the most optimal solution.
The time complexity can be improved further.
This is the most optimal approach, which stems from a mathematical insight. Instead of checking each number, we can count the factors of 5 more directly. The total number of factors of 5 in n! is the sum of the number of multiples of 5, the number of multiples of 25, the number of multiples of 125, and so on, up to n.
Algorithm
- The number of multiples of 5 up to
nisfloor(n/5). Each of these contributes at least one factor of 5. - Numbers like 25, 50, 75 are multiples of 25. They contribute an additional factor of 5. The number of such numbers is
floor(n/25). - Numbers like 125 contribute yet another factor of 5. The number of such numbers is
floor(n/125). - This pattern continues for all powers of 5.
- The total count is
count = floor(n/5) + floor(n/25) + floor(n/125) + ... - This can be implemented with a simple loop.
Walkthrough
This highly efficient method directly calculates the number of factors of 5 in n! without iterating through all numbers. The logic is as follows:
- Every multiple of 5 contributes one factor of 5. There are
n/5such numbers. - Every multiple of 25 contributes an additional factor of 5 (one was already counted in the
n/5step). There aren/25such numbers. - Every multiple of 125 contributes yet another factor of 5. There are
n/125such numbers. - We continue this process for all powers of 5 less than or equal to
n.
The total number of zeroes is n/5 + n/25 + n/125 + ...
This can be implemented with a very concise loop.
class Solution { public int trailingZeroes(int n) { int count = 0; while (n > 0) { n /= 5; count += n; } return count; }}Let's trace n = 100:
count = 0,n = 100.n = 100 / 5 = 20.count = 0 + 20 = 20.n = 20 / 5 = 4.count = 20 + 4 = 24.n = 4 / 5 = 0.count = 24 + 0 = 24.nis now 0, loop terminates. Result is 24. This approach is extremely fast and meets the follow-up requirement of a logarithmic time solution.
Complexity
Time
O(log n)
Space
O(1)
Trade-offs
Pros
Extremely fast and efficient.
Satisfies the follow-up question for a logarithmic time solution.
Elegant and concise.
Cons
The underlying mathematical reasoning might not be immediately obvious without prior knowledge.
Solutions
Solution
class Solution {public int trailingZeroes(int n) { int ans = 0; while (n > 0) { n /= 5; ans += n; } return ans; }}class Solution {public: int trailingZeroes(int n) { int ans = 0; while (n) { n /= 5; ans += n; } return ans; }};class Solution: def trailingZeroes(self, n: int) -> int: ans = 0 while n: n //= 5 ans += n return ansVideo 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.