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
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