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
    23,630
    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 02:16 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    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 03: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, 03:04 PM
  2. xor linked list
    By adramalech in forum C Programming
    Replies: 23
    Last Post: 10-14-2008, 10:13 AM
  3. Next Question...
    By Azmeos in forum C++ Programming
    Replies: 3
    Last Post: 06-06-2003, 02:40 PM
  4. C number operator question
    By unanimous in forum C Programming
    Replies: 6
    Last Post: 10-26-2001, 09:36 PM
  5. Array of boolean
    By DMaxJ in forum C++ Programming
    Replies: 11
    Last Post: 10-25-2001, 11:45 PM

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