interesting question, number of 0s at the end of N!

This is a discussion on interesting question, number of 0s at the end of N! within the C Programming forums, part of the General Programming Boards category; Hello everyone, My friend and I are discussing about an interesting question, how to calculate efficiently how many 0s are ...

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    1,579

    interesting question, number of 0s at the end of N!

    Hello everyone,


    My friend and I are discussing about an interesting question, how to calculate efficiently how many 0s are at the end of N! (1 * 2 * 3 * ... * N-1 * N).

    Our algorithm is like this,

    1. Use a loop to calculate N!
    2. Use a loop to calculate %10 result of N!, then /10 each step

    Are there any better solutions?


    regards,
    George

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,303
    As I posted in another messageboard, I think the solution is to to calculate the integer division of N by 5. This should be the number of trailing zeros in N!

    Oh, and even in your current algorithm you miss out the point that N! can be calculated directly from N without using a loop.

    My reasoning is that we get a trailing zero every time there is an implicit (2 * 5). Every time we hit an even N, we implicitly multiply by 2 yet another time, but without a corresponding multiplication by 5, there is no trailing zero appended.

    I am not a professional mathematician, and this is rather informal reasoning, so perhaps the mathematicians around here can provide a better solution or show that my reasoning is actually flawed.

    EDIT:
    Settled in that other messageboard with this link[.
    Last edited by laserlight; 06-03-2006 at 03:16 AM.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Jun 2005
    Posts
    6,659
    For positive n/5 (in integer arithmetic) will give a lower bound for the number of trailing zeros at the end of n!

    For n < 25 it is an exact lower bound. I'll leave as a challenge the analysis for n >= 25. An extra zero creeps in at n = 25 (as n is 5*5) and every multiple thereof. Similar effect occurs for n a multiple of 125 (5*5*5), 625 (5*5*5*5), .....
    Last edited by grumpy; 06-03-2006 at 04:15 AM.

  4. #4
    Registered User
    Join Date
    Dec 2005
    Location
    Australia - Melbourne
    Posts
    63
    check this site out http://www.newdream.net/~sage/old/numbers/fact.htm - "Behold! The first 999 factorials"

    you should see why we integer divide by 5 to get number of trailing zeros of n!.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. printing number from array question..
    By transgalactic2 in forum C Programming
    Replies: 41
    Last Post: 12-25-2008, 04:04 PM
  2. xor linked list
    By adramalech in forum C Programming
    Replies: 23
    Last Post: 10-14-2008, 11:13 AM
  3. Next Question...
    By Azmeos in forum C++ Programming
    Replies: 3
    Last Post: 06-06-2003, 03:40 PM
  4. C number operator question
    By unanimous in forum C Programming
    Replies: 6
    Last Post: 10-26-2001, 10:36 PM
  5. Array of boolean
    By DMaxJ in forum C++ Programming
    Replies: 11
    Last Post: 10-26-2001, 12:45 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21