Number of zeros in a Factorial

March 7, 2009 at 1:27 pm 1 comment

Its an interesting problem at:

http://www.codechef.com/problems/FCTRL/

Advertisements

Entry filed under: Uncategorized.

Good problems for programming practice II Computing small factorials

1 Comment Add your own

  • 1. Narinder Beri  |  March 7, 2009 at 1:38 pm

    The logic is that each 2 & 5 results in a 10, and hence a zero in the factorial. Since 2’s frequency is higher than 5, so we do not consider 2 but simply focus on 5.

    5! => 1
    10! => 2
    15! => 3
    etc.

    So n! will have at least n/5 zeros in it.

    The only catch is that with a multiple of 5 like 25, which has 2 5’s hidden in it, an additional zero will show up. Same goes for 100.

    So the catch junctions are:
    25, 125, 625… Each junction gives an additional zero.

    So, considering 25 and its multiples, we get 25, 50, 75,… Each of these gives 1 extra 5 on top of that given by the virtue of being a multiple of 5.
    So, considering 125 and its multiples, we get 125, 250, 375,… Each of these gives 1 extra 5 on top of that given by the virtue of being a multiple of 5 and 25.

    So, n! has n/5 + n/25 + n/125 + (till n/m becomes zero) … number of zeros in it.

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

Trackback this post  |  Subscribe to the comments via RSS Feed


Blog Stats

  • 4,036 hits

Recent Comments


%d bloggers like this: