Count the number of Trailing Zeros in the Factorial of a Given Number.
Given a number find the number of trailing zeros that the factorial of that has.
Input: n = 5Output: 1Factorial of 5 is 120 which has one trailing 0.Input: n = 20Output: 4Factorial of 20 is 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 which has 4 trailing zeroes.Input: n = 100Output: 24Factorial 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.
- Find the factorial of the given number using the carry-over approach.
- Initialize a count variable as 0.
- Use reverse for loop to check if the number is 0 or not by taking a mod of it with 10.
- If the number is zero, increase the count by 1.
- Print this count.
Below is the implementation of the above approach
Number of trailing zeros — 24
Time Complexity: O(N log N!)
Auxiliary Space: O(n)
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 = 5Prime Factors — 2x2x2x3x5Output: 1 — we have only 1 factor of 5Factorial of 5 is 120 which has only 1 trailing zero.Input: n = 11Prime Factors — 28x34x52x7Output: 2–2 factors of 5Factorial 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.
- Initialize the count variable as 0
- Use a for loop to divide the number by a power of 5–5, 25, 125, etc
- If the result of the division is greater than 1, increase the value of the count by that number.
- 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.
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