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

ReplyDeleteGreat and Useful Article.

ReplyDeleteJava Online Training

Online Java Course

Java Course Online

J2EE training

online J2EE training

Best Recommended books for Spring framework

Java Interview Questions

Java Training Institutes in Chennai

Java Training in Chennai

J2EE Training in Chennai

java j2ee training institutes in chennai

Java Course in Chennai