Thread: Last nonzero digit.

  1. #1
    Registered User
    Join Date
    Sep 2012
    Posts
    1

    Last nonzero digit.

    Hi everyone, I’m trying to solve problem in which I have to calculate the last non-zero digit of this:

    (a1+a2+a3+..+an)!/(a1!*a2!*a3!*..*an!), where 0 ≤ ai ≤ 1000000000 and n ≤ 20.

    It's obvious, that the “brutal” counting this is a bad solution (counting the one billion factorial takes too much time and memory). Another solution is an attempt to shorten. I write numerator and denominator is a simplified form (for example: 5!=1*2*3*4*5) and I’m reducing until the denominator = 1, then I’m starting to multiplies (with using my own arithmetic for large numbers) numbers that I got. This solution, in turn, doesn’t work because there is no space in the memory for a sufficiently large array (for the awarding of the numerator and denominator), on the other hand, because even after reducing, the numbers are too big for it to multiply them at the right time (for example, the medium(!) numbers – please take a look at the result: (6000!)/(1000!*2000!*3000!) - Wolfram|Alpha ). Another idea was to calculate the common logarithm of that number, but the solution isn’t valid because of too little precision of long double variable. I have no other ideas for solving this problem, so please help me with it.

    Examples:
    n=2, a1=11, a2=9
    Result: 6 (Last nonzero digit: (20!)/(11!*9!) - Wolfram|Alpha )

    n=4, a1=2, a2=5, a3=7, a4=9
    Result: 8 (Last nonzero digit: (23!)/(5!*2!*7!*9!) - Wolfram|Alpha )
    Attached Images Attached Images Last nonzero digit.-wielomian-png 

  2. #2
    Registered User
    Join Date
    Dec 2007
    Posts
    2,675

  3. #3
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Try looking at ways, on paper, to simplify ....

    (a1+a2+a3+..+an)!/(a1!*a2!*a3!*..*an!)



    There are plenty of results of combinatorics that can be used to simplify such expressions - at least, to an extent - and thereby reduce the need for brute force computation.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How to display single digit int as four digit C++ Programming
    By Sloganathan in forum C++ Programming
    Replies: 1
    Last Post: 03-06-2012, 11:30 AM
  2. Adding a number digit by digit.
    By sdfx in forum C Programming
    Replies: 4
    Last Post: 05-10-2011, 05:54 PM
  3. Read from file - 1-digit and 2-digit numbers
    By Bonaventura in forum C Programming
    Replies: 8
    Last Post: 03-06-2010, 06:33 AM
  4. Adding a Large number digit by digit
    By mejv3 in forum C Programming
    Replies: 23
    Last Post: 09-21-2007, 03:00 PM
  5. Adding a Large number digit by digit
    By mejv3 in forum C Programming
    Replies: 1
    Last Post: 09-14-2007, 03:28 AM