Last nonzero digit.

This is a discussion on Last nonzero digit. within the C++ Programming forums, part of the General Programming Boards category; Hi everyone, Iím trying to solve problem in which I have to calculate the last non-zero digit of this: (a ...

  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  

  2. #2
    a_capitalist_story
    Join Date
    Dec 2007
    Posts
    2,648

  3. #3
    Registered User
    Join Date
    Jun 2005
    Posts
    6,174
    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%.

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, 10: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, 05: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

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