Question Write a program that can compute the last non-zero digit of any factorial for ( 0 <= N <= 10000). For example, if your program is asked to compute the last nonzero digit of 5!, your program should produce 2 because 5! = 120, and 2 is the last nonzero digit of 120.
Solution:Well if one has thoroughly gone through the post,
the answer is easy to arrive at.Since the question asks only about the last non Zero digit,we need not bother about calculating the whole factorial and can just keep track of last nonzero digit by writing nonzerodigit(N)=nonzerodigit(N* nonzerodigit(N-1)).
Here follows the last nonzero digits of first 5 numbers.
N factorial Last Non Zero Digit
1! 1
2! nonzerodigit(2*1)=2
3! nonzerodigit(3*2)=6
4! nonzerodigit(4*6)=4
5! nonzerodigit(4*5)=2!!!(one gets zero if only the last digit is tracked)
So ,it should be clear the mere tracking of last digit is not enough but we need to track some K digits in each factorial.
So we track the last K digits of factorial of each number and store them in a vector V.
At the same time we want to have minimum K.
A brief thought would suggest that we should track of that many no of digits such that for all numbers <=1000 we should never encounter a 0 in V.
This means K is 1+ maximum no of zeros one would encounter in N! for N<=1000.
In this particular case K is 1+5 (maximum no of zeros is 5 since 5^5=3125 and 5^6>10000).
So track the last 6 digits of each of the factorials.Thus we arrived at the solution!!
Question If you have already solved the above problem, then give a generalized method to find the last X non-zero digits of N factorial
Solution:This question is similar to the above one except that we need to track X-1 more digits of N! .
so answer to this is X+No of zeros in N! factorial.
Click here for more questions
can you come up with some clear idea of how u saying that maximum number of zeros possible is 5. ie how you choosing 5^6 and not more than 6.
ReplyDeleteWe could find the last k non-zero digits of factorial quickly at the link http://zdu.spaces.live.com/blog/cns!C95152CB25EF2037!125.entry.
ReplyDeleteActually it's even easier to do, you just have to check how many multiples of 5 has N and that's the number of zeros the factorial will have...
ReplyDeleteFor example, if you want the factorial of 27, you know that 27! = 27*26*25*23*...*1, whenever you multiply a multple of 5 (25, 20, 15, 10 and 5 in this case) by any even number the result in a multiple of 10, adding an extra 0 to the count.
In fact 10 and 20 are already multiples of 10, so they add the extra 0 when they get multiplied.
Because of this you can calculate the number of multiples of 5 (int zeros = n / 5;), resulting in the number of zeros the factorial will have, so you'll have to trace zeros+1 numbers of the factorial.
In fact you could simply divide by ten every time you passed a multiple of 5 and you wouldn't have to trace more than 2 digits
The general equation presented is K = X + nZeros(n!). But nZeros(1000!) = 249, as calculated in the other post, not 5.
ReplyDeleteCould you explain this better, plz?
what if n is of order 10^100
ReplyDelete