Factorial Trailing Zeroes Python Solution

Tested Python solution for LeetCode 172 with 26 pytest cases. Generate a practice environment with lcpy.

LeetCode 172, Medium. Topics: Math. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 26 parametrized pytest cases, and a playground notebook:

lcpy gen -n 172   # by problem number
lcpy gen -s factorial_trailing_zeroes   # by problem name

​

Problem

Given an integer <code>n</code>, return <em>the number of trailing zeroes in </em><code>n!</code>.

<p>Note that <code>n! = n * (n - 1) * (n - 2) * … * 3 * 2 * 1</code>.</p>

​

Examples

Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Input: n = 0
Output: 0

​

Constraints

• 0 <= n <= 10^4

<p><strong>Follow up:</strong> Could you write a solution that works in logarithmic time complexity?</p>

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(log n) (base 5)
    # Space: O(1)
    def trailing_zeroes(self, n: int) -> int:
        zero_count = 0
        while n > 0:
            n //= 5
            zero_count += n
        return zero_count

​

Complexity

Time	Space
O(log n) (base 5)	O(1)

​

Tags