## Problem Statement

Given an integer `n`

, our task is to write a function that returns the **count of trailing zeros** in `n!`

. Here `n!`

is the factorial of a number `n`

which is the product of all numbers in the range $[1, n]$.

## Example :

```
Input: n = 3
Output: 0
Input: n = 5
Output: 1
Input: n = 20
Output: 4
```

## Explanation

**Example – 1 :**

When $n = 3$, Factorial of `3`

is `6`

, which has no trailing zeros in factorial.

**Example – 2 :**

When $n = 5$, Factorial of `5`

is `120`

, which has no trailing zeros in factorial.

**Example – 3 :**

When $n = 20$, Factorial of `20`

is `2432902008176640000`

, which has four trailing zeros in factorial.

## Constraints

$0 <= n <= 10^{4}$

## Approach – 1 : Naive Approach

### Algorithm :

In this approach, the intuition is to calculate the value of `n!`

and then count the number of trailing zeros in factorial. The number of zeros can be measured by repeatedly dividing the value of the factorial by `10`

until the last digit becomes non-zero.

### Implementation

**Implementation of Naive Approach in C++ :**

```
#include <iostream>
using namespace std;
int trailingZeros(int n) {
int fact = 1;
```*// calculating factorial*
for (int i = 1; i <= n; i++) {
fact = fact * i;
}
int zeros = 0;
*// counting the number of trailing zeros*
while (fact % 10 == 0) {
zeros++;
fact = fact / 10;
}
return zeros;
}
int main() {
cout << trailingZeros(6);
return 0;
}

**Output :**

```
1
```

**Implementation of Naive Approach in Java :**

```
import java.io.*;
public class Main {
public static int trailingZeros(int n) {
int fact = 1;
```*// calculating factorial*
for (int i = 1; i <= n; i++) {
fact = fact * i;
}
int zeros = 0;
*// counting the number of trailing zeros*
while (fact % 10 == 0) {
zeros++;
fact = fact / 10;
}
return zeros;
}
public static void main(String[] args) {
System.out.println(trailingZeros(6));
}
}

**Output :**

```
1
```

**Implementation of Naive Approach in Python :**

```
def trailingZeros(n):
fact = 1
zeros = 0
```*# calculating factorial*
for i in range(1, n + 1):
fact = fact * i
*# counting the number of trailing zeros*
while (fact % 10) == 0:
fact = fact // 10
zeros += 1
return zeros
print(trailingZeros(20))

**Output :**

```
4
```

### Complexity Analysis

**Time Complexity :**

- Since we are iterating over
`n`

times to calculate the factorial value, the Time Complexity for calculating the number of trailing zeros in factorial is $O(n)$.

**Space Complexity :**

- While no auxiliary space is required to calculate the number of trailing zeros in factorial, Space Complexity is $O(1)$.

## Approach – 2 : Optimal Approach

### Algorithm :

The above approach can lead to an overflow in case of bigger numbers as factorial could be a really big number. So, the intuition for a better approach is to consider that a trailing zero is produced when a number is multiplied by `10`

. The prime factors of `10`

are `2`

and `5`

.

So, our task now becomes to just count the number of `2s`

and `5s`

.

**Let us consider an example, where n = 5 :**`5! = 2 x 2 x 2 x 3 x 5`

The number of trailing zeros in the factorial of `5`

will be `1`

because only one pair of `2`

and `5`

can be made from one `5`

and three `2s`

in the prime factors of `5!`

.

In the above example, we can see that the **number of 2s** in prime factors is always more than or equal to the **number of 5s**.

So if we count the **number of 5s** in the prime factors, our task is done. But how to calculate the number of `5s`

in prime factors of `n!`

? An easy method of doing this would be using **Legendre’s Formula**, which is used to get the highest power of a prime number p in `n!`

.

Here, $V_p(n!)$ represents the highest power in `p`

, in a way that $p^n$ divides `n!`

where `p`

is a prime number.

$[n]$ is the greatest integer function. $[4.99] = 4, [4.01] = 4, [-3.01] = 4$

The above formula will compute the exact number of `5s`

in `n!`

as it will consider all multiples of `5`

that are less than `n`

. This will also consider all higher power multiples of `5`

i.e `25`

, `125`

, etc.

Therefore, the formula gets transformed to the following for calculating **trailing zeros in factorial** of a number `n`

:

Where `k`

= floor of $log_5n$.

**Let us now solve a few examples using this formula :**

**Example – 1 :**

number of trailing zeros in `24!`

will be

$[24/5] = [4.8] = 4$ trailing zeros

**Example – 2 :**

number of trailing zeros in `123!`

will be :

$[123/5] = [24.6] = 24$ trailing zeros.

$[123/25] = [4.92] = 4$ trailing zeros.

Therefore, `123!`

has a total of `28`

trailing zeros

**The final algorithm is :**

- Create a function
`trailing_zeros(int number)`

that takes an integer`n`

and returns the count of trailing zeros in factorial of`n`

. - Check for the edge case where, if
`n < 0`

, return`-1`

. - Initialize
**count**=`0`

. - Traverse using a for loop and divide the number
`n`

by powers of`5`

at every iteration. - If
`number/i`

is greater than or equal to`1`

, add`number/i`

to count. - At the end of for loop, the return count as result.

### Implementation

**Implementation of Optimal Approach in C++ :**

```
#include <iostream>
using namespace std;
int trailingZeros(int n) {
```*// in case of negative numbers*
if (n < 0)
return -1;
*// initializing count variable*
int count = 0;
*// dividing n by powers of 5 and updating count*
for (int i = 5; n / i >= 1; i *= 5)
count += n / i;
return count;
}
int main() {
int n = 100;
cout << "Count of trailing 0s in " << 100 << "! is "<< trailingZeros(n);
return 0;
}

**Output :**

```
The count of trailing 0s in 100! is 24
```

**Implementation of Optimal Approach in Java :**

```
import java.io.*;
class Main {
static int trailingZeros(int n) {
```*// in case of negative numbers*
if (n < 0) return -1;
*// initializing count variable*
int count = 0;
*// dividing n by powers of 5 and updating count*
for (int i = 5; n / i >= 1; i *= 5) count += n / i;
return count;
}
public static void main(String[] args) {
int n = 100;
System.out.println(
"Count of trailing 0s in " + n + "! is " + trailingZeros(n)
);
}
}

**Output :**

```
The count of trailing 0s in 100! is 24
```

**Implementation of Optimal Approach in Python :**

```
def trailingZeros(n):
```*# in case of negative numbers*
if(n < 0):
return -1
*# initializing count variable*
count = 0
*# dividing n by powers of 5 and updating count*
while(n >= 5):
n //= 5
count += n
return count
n = 100
print("Count of trailing 0s in 100! is", trailingZeros(n))

**Output :**

```
The count of trailing 0s in 100! is 24
```

### Complexity Analysis

**Time Complexity :**

- In this approach,
`n`

is divided by`5`

till it becomes`0`

. Therefore, the number of iterations till which the program will execute is equal to $floor(log_5n)$, which makes the Time Complexity as $O(log_5n)$. **Space Complexity :**- Similar to the previous approach no auxiliary space is required to calculate the number of trailing zeros in factorial, Space Complexity is $O(1)$.

## Conclusion

- The drawback of using the naive approach is that it calculates the factorial of given
`n`

before computing the result, whose value can grow very large and can cause an overflow issue. - The optimal approach uses
**Legendre’s Formula**to compute the highest power of any prime number`p`

in`n!`

, which in this problem calculates the highest power of`5`

in`n!`

. - The time and Space Complexity of the Optimal Approach to calculate the number of trailing zeros in factorial is $O(log_5n)$ and $O(1)$ respectively.