# 172-factorial-trailing-zeroes


Try it on <a href='https://leetcode.com/problems/172-factorial-trailing-zeroes'>leetcode</a>

## Description
<div class="description">
<div><p>Given an integer <code>n</code>, return <em>the number of trailing zeroes in </em><code>n!</code>.</p>

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

<p>&nbsp;</p>
<p><strong>Example 1:</strong></p>

<pre><strong>Input:</strong> n = 3
<strong>Output:</strong> 0
<strong>Explanation:</strong> 3! = 6, no trailing zero.
</pre>

<p><strong>Example 2:</strong></p>

<pre><strong>Input:</strong> n = 5
<strong>Output:</strong> 1
<strong>Explanation:</strong> 5! = 120, one trailing zero.
</pre>

<p><strong>Example 3:</strong></p>

<pre><strong>Input:</strong> n = 0
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= n &lt;= 10<sup>4</sup></code></li>
</ul>

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

## Solution(Python)
```Python
class Solution:
    def trailingZeroes(self, n: int) -> int:
        return self.math(n)

    # Time Complexity1: O(n)
    # space Complexity: O(1)
    # overflow error for n > 20
    def bruteforce(self, n):
        # generate factorial of number
        fact = 1
        for i in range(2, n + 1):
            fact *= i
        # calculate trailing zeros
        cnt = 0
        rem = 0
        while fact >= 0 and rem == 0:
            rem = fact % 10
            fact = fact // 10
            if rem == 0:
                cnt += 1
        return cnt

    # prime factor of 10 = 2 aND 5
    # even numbers has 2 and onlyconsider 5
    # trailing zeros = n/5 + n/25 + n/125
    # Time Complexity: O(log_5_n )
    def math(self, n):
        if n <= 0:
            return 0

        cnt = 0

        while n >= 5:
            n //= 5
            cnt += n
        return cnt

```