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

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