Find number of trailing zeros in factorial

Learn how to create an algorithm to find the number of trailing zeros in a factorial of a given number.

Example

Input:
5
10

Output:
1
2

The factorial of 5 is 5 * 4 * 3 * 2 * 1 = 120 so the number of zeros at the end is 1. Likewise 10! is 3628800 so the trailing zeros are 2.

Finding the number of trailing zeros in a factorial.

One way to solve this problem is to

1. Find the factorial of the given number.
2. And then calculate the number of trailing zeros.

But the problem with this approach is that storing the value of large factorial are not easy. Either we use an list and do the factorial and store the numbers or use better structures to store the large numbers. which will take O(n) time and O(log(n!)) space.

There is another better way which works in O(log(n)).

If you closely look the factorials of the numbers you will find that there is a pattern in which numbers of zeros are present.

The number of zeros are increased for every power of 5. It follows the following pattern n/5 + n/25 + n/125 + n/625....

Example

If the n is 24 then it less than next multiple of 25 so the total numbers of zero will be Math.floor(24 / 5) = 4.

If n is 110 then we can use the above pattern to calculate the number of zeros. As it is less than 125 then

Math.floor(n / 5) + Math.floor(n / 25)
=
22 + 4
=
26

Now we have to convert the above pattern to code.

Implementation

• We iterate the loop till the number is less than the next multiple of 5.
• Then divide the original number with the given multiple of 5 and keep addding its output.

const trailingZeroes = (n) => {
    
    if(n < 5){
        return 0;
    }
    
    let output = 0;
    
    //Track the multiples
    let x = 5;
    
    //Loop till the number is less than next multiple
    while(x <= n){
        output += Math.floor(n / x);
        x *= 5;
    }
     
    //return the output
    return output;

};

Input:
console.log(trailingZeroes(13030));

Output:
3255

Time complexity: O(log5(n));
In each iteration we increment to the next power of 5.
Space complexity: O(1).