Factorial Trailing Zeroes Leetcode Solution

Problem Statement

In this problem we have to find out how many trailing zeroes will be there in n!

Given n as input.

 

Like there is one trailing zero in 5!

5! = 5*4*3*2*1 = 120

Example

n = 3

0

Explanation: 3! = 6, no trailing zero

n = 0

0

Explanation: 0! = 1, no trailing zero

 

 

 

To find the number of trailing zeroes in n! , a simple way is to calculate the n! and check how many zeroes are there at the end. This we can do simply by checking if dividing the number by 10 we get remainder 0 and then removing the last zero by dividing it by 10. We can count this till we get remainder equal to zero each time.

 

But this approach is not practical with simple integers because we know n! is a very big number. In C++ and Java simple integer size is 64-bit at best which can only store an integer to a limit of 2^63 - 1. Which is approximate to 10^18. In java we can use BigInteger class to store big numbers like n!. But this brute force approach has large time and space complexity.

 

Here we are going to discuss efficient solution for finding the trailing zeroes in n!

Approach 1 (Counting factors of 5)

We can say that total number of trailing zeroes will be equal to count of how many times 10 is factor of that number. And we know that every 10 is formed of the product of two prime numbers 2 and 5.

So if we find out how many factors of 2's are there in the number. Similarly how many factors of 5's are there.

 

www.tutorialcup.com/leetcode-solutions/factorial-trailing...

Done