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.
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 )
Try looking at ways, on paper, to simplify ....
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.