Trailing Zeros in Factorial

Description

Problem Description: We are given a number. The task is to find the Number of Trailing Zeros in the factorial of the number.

The Trailing Zeros are the Zeros, which appear at the end of a number(factorial in that case)

Examples :

Input: 5
Output: 1
// Factorial of 5 = 5*4*3*2*1 = 120, which has one trailing 0.

Input: 20
Output: 4
// Factorial of 20 = 20*19*18*.... 3*2*1 = 2432902008176640000 which has 4 trailing zeroes.

Input: 100
Output: 24

Approach

Naive Approach:

This method appears to be an effective way to count the number of zeros. It involves calculating the factorial of N and incrementing a count for each zero encountered until the factorial modulo 10 is not equal to 0.

Time Complexity: O(N)

However, when calculating the factorial of a large number like 100, we run into a problem. The factorial of 100 has 99 digits, which exceeds the capacity of many data types and can lead to an overflow error. So, what should we do in such cases?

Efficient Approach

If you want to count the number of trailing zeros in the factorial of a number while avoiding overflow.

Since 10 can be factored into 2 * 5, we need to count the number of pairs of 2s and 5s in the factorial.

Here's the simplified formula for counting trailing zeros:

Trailing 0s in n! = floor(n/5) + floor(n/25) + floor(n/125) + …

Time Complexity: O(log5N)

In conclusion

If you are interested in how to do you find the time complexity of an algorithm give me feedback.

Don't forget LIKE and COMMENT