Count the number of Trailing Zeros in the Factorial of a Given Number.

Problem Statement

Given a number find the number of trailing zeros that the factorial of that has.

Examples :

Input: n = 5
Output: 1
Factorial of 5 is 120 which has one trailing 0.
Input: n = 20
Output: 4
Factorial of 20 is 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 which has 4 trailing zeroes.
Input: n = 100
Output: 24
Factorial of 20 is 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 which has 24 trailing zeroes.

In this blog, we will be discussing two ways through which we can calculate the number of these trailing zeros.

Brute Force Approach

The brute force approach is the first approach that comes to mind and in our case, the first approach that comes to mind is to first find the factorial of the given number and then calculate the number of trailing zeros.

As we already know that simple iterative and recursive methods will not be useful to find the factorial of large numbers like 100, so we will be using the carry-over approach from the get-go so that we can calculate the trailing zeros of every positive number.

Algorithm

1. Find the factorial of the given number using the carry-over approach.
2. Initialize a count variable as 0.
3. Use reverse for loop to check if the number is 0 or not by taking a mod of it with 10.
4. If the number is zero, increase the count by 1.
5. Print this count.

Below is the implementation of the above approach

Output

Number of trailing zeros — 24

Time Complexity: O(N log N!)

Auxiliary Space: O(n)

Efficient Approach

We know that the factorial of a number is the product of that number with other natural numbers which are less than the number and greater than 0, and in maximum cases that number has some trailing zeros. The reason behind this is the presence of the number 10 or its factors 2 and 5.

If we do the Prime factorization of the factorial we will get the count of 2s and 5s which we can use to find the number of trailing zeros.

Let’s take an example to understand

Input: n = 5
Prime Factors — 2x2x2x3x5
Output: 1 — we have only 1 factor of 5
Factorial of 5 is 120 which has only 1 trailing zero.
Input: n = 11
Prime Factors — 28x34x52x7
Output: 2–2 factors of 5
Factorial of 20 is 39916800 which has 2 trailing zeroes.

From the above examples, it is clear that finding factors of 5 in the factorial of a number will give us the exact number of trailing zeros the factorial of that number had. Below are the steps we have to code to find the number of trailing zeros.

Algorithm

1. Initialize the count variable as 0
2. Use a for loop to divide the number by a power of 5–5, 25, 125, etc
3. If the result of the division is greater than 1, increase the value of the count by that number.
4. Print or return count as this will be our answer or the number of trailing zeros

The beauty of this approach is we don’t have to find the factorial of the number first to calculate the trailing zeros.

Output

The number of trailing zeros is 24

Time Complexity: O(log n)

Auxiliary Space: O(1)

Well, it is quite clear that the second approach has a clean victory when it comes to finding the number of trailing zeros in terms of both time and space complexity. Where the brute force approach was taking a time of N log N and space complexity of O(n), the other approach took only log N time and linear space to find the number of trailing zeros of the factorial of the given number.

You can go through some of my other projects as well

1. Calculate Factorial of a given number
2. Merge two Sorted Arrays
3. How to Rotate an Array