top of page

### Looking to master object-oriented and system design for tech interviews or career growth?

• Improve your system design and machine coding skills.

• Study with our helpful resources.

**We're in beta mode and would love to hear your feedback.

Search

# 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)`

Code in C++

Tags:

bottom of page