Trailing Zeros in Factorial

Problem Statement

Given an integer n, our task is to write a function that returns the count of trailing zeros in n!. Here n! is the factorial of a number n which is the product of all numbers in the range $[1, n]$.

Example :

Explanation

Example - 1 :
When $n = 3$, Factorial of 3 is 6, which has no trailing zeros in factorial.

Example - 2 :
When $n = 5$, Factorial of 5 is 120, which has no trailing zeros in factorial.

Example - 3 :
When $n = 20$, Factorial of 20 is 2432902008176640000, which has four trailing zeros in factorial.

Constraints

$0 <= n <= 10^{4}$

Approach - 1 : Naive Approach

Algorithm :

In this approach, the intuition is to calculate the value of n! and then count the number of trailing zeros in factorial. The number of zeros can be measured by repeatedly dividing the value of the factorial by 10 until the last digit becomes non-zero.

Implementation

Implementation of Naive Approach in C++ :

Output :

Implementation of Naive Approach in Java :

Output :

Implementation of Naive Approach in Python :

Output :

Complexity Analysis

Time Complexity :

• Since we are iterating over n times to calculate the factorial value, the Time Complexity for calculating the number of trailing zeros in factorial is $O(n)$.

Space Complexity :

• While no auxiliary space is required to calculate the number of trailing zeros in factorial, Space Complexity is $O(1)$.

Approach - 2 : Optimal Approach

Algorithm :

The above approach can lead to an overflow in case of bigger numbers as factorial could be a really big number. So, the intuition for a better approach is to consider that a trailing zero is produced when a number is multiplied by 10. The prime factors of 10 are 2 and 5.

So, our task now becomes to just count the number of 2s and 5s.

Let us consider an example, where n = 5 :
5! = 2 x 2 x 2 x 3 x 5

The number of trailing zeros in the factorial of 5 will be 1 because only one pair of 2 and 5 can be made from one 5 and three 2s in the prime factors of 5!.

In the above example, we can see that the number of 2s in prime factors is always more than or equal to the number of 5s.

So if we count the number of 5s in the prime factors, our task is done. But how to calculate the number of 5s in prime factors of n!? An easy method of doing this would be using Legendre’s Formula, which is used to get the highest power of a prime number p in n!.

Here, $V_p(n!)$ represents the highest power in p, in a way that $p^n$ divides n! where p is a prime number.

The above formula will compute the exact number of 5s in n! as it will consider all multiples of 5 that are less than n. This will also consider all higher power multiples of 5 i.e 25, 125, etc.

Therefore, the formula gets transformed to the following for calculating trailing zeros in factorial of a number n :

Where k = floor of $log_5n$.

Let us now solve a few examples using this formula :

Example - 1 :
number of trailing zeros in 24! will be $[24/5] = [4.8] = 4$ trailing zeros

Example - 2 :
number of trailing zeros in 123! will be : $[123/5] = [24.6] = 24$ trailing zeros. $[123/25] = [4.92] = 4$ trailing zeros.

Therefore, 123! has a total of 28 trailing zeros

The final algorithm is :

• Create a function trailing_zeros(int number) that takes an integer n and returns the count of trailing zeros in factorial of n.
• Check for the edge case where, if n < 0, return -1.
• Initialize count = 0.
• Traverse using a for loop and divide the number n by powers of 5 at every iteration.
• If number/i is greater than or equal to 1, add number/i to count.
• At the end of for loop, the return count as result.

Implementation

Implementation of Optimal Approach in C++ :

Output :

Implementation of Optimal Approach in Java :

Output :

Implementation of Optimal Approach in Python :

Output :

Complexity Analysis

Time Complexity :

• In this approach, n is divided by 5 till it becomes 0. Therefore, the number of iterations till which the program will execute is equal to $floor(log_5n)$, which makes the Time Complexity as $O(log_5n)$.

Space Complexity :

• Similar to the previous approach no auxiliary space is required to calculate the number of trailing zeros in factorial, Space Complexity is $O(1)$.