# LeetCode 172: Factorial Trailing Zeroes

## Problem Restatement

We are given a non-negative integer:

```python
n
```

We need to return the number of trailing zeroes in:

```python
n!
```

where:

```python
n! = 1 * 2 * 3 * ... * n
```

A trailing zero is a zero at the end of the decimal representation.

For example:

```python
1200
```

has:

```python
2
```

trailing zeroes.

The problem asks us to compute the answer without explicitly calculating the factorial. The constraints allow values up to `10^4` on LeetCode, though the mathematical method works for much larger numbers. ([leetcode.com](https://leetcode.com/problems/factorial-trailing-zeroes/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | Number of trailing zeroes in `n!` |
| Trailing zero | A factor of `10` at the end |
| Important restriction | Do not compute the factorial directly |

Example function shape:

```python
def trailingZeroes(n: int) -> int:
    ...
```

## Examples

Example 1:

```python
n = 3
```

Compute:

```python
3! = 6
```

No trailing zeroes.

Return:

```python
0
```

Example 2:

```python
n = 5
```

Compute:

```python
5! = 120
```

There is one trailing zero.

Return:

```python
1
```

Example 3:

```python
n = 10
```

Compute:

```python
10! = 3628800
```

There are two trailing zeroes.

Return:

```python
2
```

## First Thought: Compute the Factorial

One possible idea is:

```python
factorial = 1

for i in range(1, n + 1):
    factorial *= i
```

Then repeatedly divide by `10`.

This works for small numbers, but factorials grow extremely quickly.

For example:

```python
100!
```

already has a huge number of digits.

The problem expects a mathematical solution.

## Key Insight

A trailing zero comes from a factor of:

```python
10
```

And:

```python
10 = 2 * 5
```

So the number of trailing zeroes equals the number of pairs:

```python
(2, 5)
```

inside the prime factorization of `n!`.

In factorials, factors of `2` are much more common than factors of `5`.

So the limiting factor is the number of `5`s.

Therefore:

The number of trailing zeroes equals the total number of factors of `5` inside `n!`.

## Counting Factors of 5

Every multiple of `5` contributes at least one factor of `5`.

Examples:

| Number | Factors of 5 contributed |
|---|---:|
| `5` | `1` |
| `10` | `1` |
| `15` | `1` |
| `20` | `1` |
| `25` | `2` |
| `125` | `3` |

Notice:

```python
25 = 5 * 5
```

contributes two factors of `5`.

And:

```python
125 = 5 * 5 * 5
```

contributes three.

So we must count all powers of `5`.

The formula becomes:

```python
n // 5
+ n // 25
+ n // 125
+ ...
```

until the power exceeds `n`.

## Why the Formula Works

Suppose:

```python
n = 25
```

Multiples of `5`:

```python
5, 10, 15, 20, 25
```

That gives:

```python
25 // 5 = 5
```

factors of `5`.

But `25` contributes an extra factor:

```python
25 = 5 * 5
```

So add:

```python
25 // 25 = 1
```

Total:

```python
5 + 1 = 6
```

Indeed:

```python
25!
```

has exactly `6` trailing zeroes.

## Algorithm

Initialize:

```python
answer = 0
```

While `n > 0`:

1. Divide `n` by `5`.
2. Add the quotient to the answer.
3. Continue with the smaller quotient.

Return the answer.

## Walkthrough

Use:

```python
n = 100
```

First division:

```python
100 // 5 = 20
```

Add:

```python
answer = 20
```

Second division:

```python
20 // 5 = 4
```

Add:

```python
answer = 24
```

Third division:

```python
4 // 5 = 0
```

Stop.

Return:

```python
24
```

So:

```python