# 172 Factorial Trailing Zeroes

Given an integern, return the number of trailing zeroes inn!.

**Note:**Your solution should be in logarithmic time complexity.

**The Idea:** First lets take a look at the factorial sequence and see if we can notice a pattern.

```
0    1
1    1
2    2
3    6
4    24
5    120
6    720
7    5040
8    40320
9    362880
10    3628800
11    39916800
12    479001600
13    6227020800
14    87178291200
15    1307674368000
16    20922789888000
17    355687428096000
18    6402373705728000
19    121645100408832000
20    2432902008176640000
21    51090942171709440000
22    1124000727777607680000
23    25852016738884976640000
24    620448401733239439360000
25    15511210043330985984000000
26    403291461126605635584000000
27    10888869450418352160768000000
```

If we just count the zeros we can see that it follows to be 0,0,0,0,0,1,1,1,1,1,2,2,2,2,2 .... and so fourth. That alone can be modeled with a linear function, `f(x) = floor(x/5)`

![](/files/-LoJIfDNHUPmk_QKhWL3)

However, there is one additional thing. Notice how there is a jump of an additional zero on `25!`. It will follow that every 5^n there will be another one of this jumps, and they add on to the previous, we can fix our model now to be `f(x) = floor(x/5) + floor(x/25)`

![](/files/-LoJIfDPnSRREkquoenp)

But to get this right, we will need to add `floor(x/pow(5,n)` dependently on just how large n actually gets.

`f(x) = floor(x/5) + floor(x/25) + floor(x/125) + ....+ floor(x/pow(5, n))` is the true solution.

**Complexity:** Because our power number will expand exponentially, we will reach our target in logarithmic time, and so there will only be a logarithmic amount of summations. O(logn) time and space, but O(1) space iterative

**Recursive**

```python
import math

class Solution:
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 4:
            return 0
        elif n <= 9:
            return 1

        return math.floor(n / 5) + self.trailingZeroes(math.floor(n / 5))
```

**Iterative**

```python
import math

class Solution:
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """

        five_pow = 1
        current_power = math.pow(5, five_pow)
        total_zeros = 0

        while current_power <= n:
            total_zeros += math.floor(n/current_power)
            five_pow += 1
            current_power = math.pow(5, five_pow)

        return total_zeros
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/172-factorial-trailing-zeroes.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.