# Trailing Zeros in Factorial InterviewBit Solution

**Problem: **__Trailing Zeros in Factorial__

**Problem Description:**

Given an integer **A**, return the number of trailing zeroes in A!.

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

**Problem Constraints:**

`1 <= A <= 10000`

**Input Format:**

`First and only argument is integer A.`

**Output Format:**

`Return an integer, the answer to the problem.`

**Example Input**

```
Input 1: A = 4
Input 2: A = 5
```

**Example Output:**

```
Output 1: 0
Output 2: 1
```

**Example Explanation:**

```
Explanation 1: 4! = 24
Explanation 2: 5! = 120
```

## Approach

Since we want to count trailing zeroes, and we know that when an even number is multiplied by a multiple of 5, then it results in a number which has the count of trailing zeroes greater than 1.

And also we know that number of even number will always be greater than the multiple of 5 in the range from 1 to N, where N > 1.

Considering the above facts, we just have to check the multiple of fives that are lesser than N. So let's check for an example,

```
Example 1:
N = 12
N! = 12! = 479,001,6
```**00**
Number of multiples of 5 below 12 are 5 & 10.
Therefore, number of trailing zeroes = 2.

```
Example 2:
N = 30
N! = 30! = 265,252,859,812,191,058,636,308,48
```**0****,****000****,****000**
Number of multiples of 5 below 30 are 5, 10, 15, 20, 25 & 30.
So, number of trailing zeroes should be 6, but we have 7 here.
Because 25 * 4 = 100. // 2 trailing zeroes and we have counted only 1

So we notice above that we have to check for the power of 5 as well.

```
5 * 2 = 10
25 * 4 = 100
125 * 8 = 1000
And so on...
```

For each power of 5 in the range, we have to increment count as well.

## Time & Space Complexity

`Time Complexity: O(log5(N))`

- Here the base is 5 because we are dividing the number N with 5 in each iteration.

`Space Complexity: O(1)`

**Solution:**

Code in C++