# 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,600
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,480,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++

## Commentaires