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++