172. Factorial Trailing Zeroes
Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 1
Acceptance rate: 38.8%
Problem Breakdown
The problem asks us to determine the number of trailing zeroes in the factorial of a given integer n. The input is an integer n where 0 <= n <= 10^4, and the output should be the count of trailing zeroes in n!.
Inputs:
- An integer
n
Outputs:
- An integer representing the number of trailing zeroes in
n!
Implicit Constraints or Tricky Edge Cases:
- If
nis 0, the factorial is 1, which has no trailing zeroes. - The problem requires a solution with logarithmic time complexity.
Intuition
The brute-force approach would involve calculating the factorial of n and then counting the number of trailing zeroes. However, this approach is inefficient due to the rapid growth of factorials and potential for integer overflow.
A key insight is that trailing zeroes in a number are created by factors of 10. Since 10 is the product of 2 and 5, and there are always more factors of 2 than 5 in factorials, the number of trailing zeroes is determined by the number of times 5 is a factor in the numbers from 1 to n.
To count these factors efficiently, we can repeatedly divide n by powers of 5 (i.e., 5, 25, 125, etc.) and sum up the quotients. This approach leverages the fact that each multiple of 5 contributes at least one factor of 5, multiples of 25 contribute an additional factor, and so on.
Approach
We will use a mathematical approach to count the number of factors of 5 in n!. The algorithm involves:
- Initialize a counter to zero.
- For each power of 5 (starting from 5), divide
nby that power and add the quotient to the counter. - Continue this process until the power of 5 exceeds
n. - Return the counter as the result.
This approach ensures logarithmic time complexity because we are effectively halving the problem size with each iteration.
Complexity Analysis
- Time Complexity: O(log₅(n)), where n is the input number. This is because we divide
nby increasing powers of 5 until the power exceedsn. - Space Complexity: O(1), as we only use a constant amount of extra space for variables.
Solution
def trailingZeroes(n: int) -> int:
count = 0
power_of_5 = 5
while n >= power_of_5:
count += n // power_of_5
power_of_5 *= 5
return count
Edge Cases Handled
- n = 0: The factorial of 0 is 1, which has no trailing zeroes. The algorithm correctly returns 0.
- n = 1: The factorial of 1 is 1, which has no trailing zeroes. The algorithm correctly returns 0.
- n = 5: The factorial of 5 is 120, which has one trailing zero. The algorithm correctly returns 1.
- n = 25: The factorial of 25 includes multiple factors of 5 (from numbers like 5, 10, 15, 20, and 25), resulting in six trailing zeroes. The algorithm correctly returns 6.
This solution efficiently counts the number of trailing zeroes in n! using a logarithmic approach, making it suitable for large values of n up to 10^4.