# Trailing Zeros

## Problem

Write an algorithm which computes the number of trailing zeros in `n`

factorial.

### Example

`11! = 39916800`

, so the out should be `2`

.

## Solution

Trailing zeros depends on how many `2`

and `5`

in the factors, and there are always more `2`

than `5`

, so we only need to count how many `5`

s, every `5`

will result in one `0`

.

How to count `5`

?

The example `11! = 11 x 10 x ... x 5 x 4 x 3 x 2 x 1`

, only `10`

and `5`

have `5`

in factors, so the result is 2.

Another example: `101! = 101 x 100 x 99 x ... x 1`

, `100, 95, 90 ... 15, 10, 5`

has one `5`

, and `100, 75, 50, 25`

has another `5`

. The easy way to compute the first `5`

is `101 / 5 = 20`

, then to compute the second `5`

, we can "shrink" the numbers by `5`

to `20, 15, 10, 5`

, if they still have `5`

in factors we count another one, so `101 / 5 / 5 = 4`

. So the overall is:

```
while (n > 0) {
cnt += n / 5;
n /= 5;
}
```