Factorial Trailing Zeroes

Posted on

Problem

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Solution

0 in the number is coming from 10. 10 = 2 * 5. So must count the number of 2*5 pairs in n!.

The naive way is to use n! % 5 each time, add the counter until n! % 5 != 0. However, n! is easy to overflow. So this problem we cannot do the calculation of n!.

To count the number of 5, we can just use the result of n/5.                                                          i.e. 5! -> 5/5 = 1        10! -> 10/5 = 2  However, for 25! or 125! or (5^x)!, this includes 25, 125, some 5^x numbers contain more than one 5. So need to add these concealed 5 together. Therefore, the total number of 5 is n/5 + n/25 + n/125 + …. until 5^x > n.

After the judgement of OJ, when n is too big, it means 5^x may get too big to overflow, so the parameter to store this number (i) must be set as long type to avoid overflow.

screen-shot-2016-10-16-at-5-18-04-pm

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s