I need an efficient program to print last non zero digit of n!...n can be fairly large number

Printable View

- 04-22-2009Tanuj_TanmayProgram to print last non zero digit of n!
I need an efficient program to print last non zero digit of n!...n can be fairly large number

- 04-22-2009matsp
How large is "fairly large"?

--

Mats - 04-22-2009Snafuist
Obviously, you need to count the sum of the multiplicities of the powers of 10 which divide n. In mathematical terms, the following expression computes this number: sum(i=1...k)(floor(n/5^i)) for 5^k < n < 5^(k+1).

But since I believe that you got the problem from Project Euler, I don't want to prevent you from having the delightful experience of finding a solution that you can understand all by yourself.

Greets,

Philip

EDIT: oops, I didn't notice the "non" in "non zero digit", but from what I said, you can easily derive a solution to obtain the last non-zero digit. - 04-22-2009Tanuj_Tanmay
- 04-22-2009EVOEx
- 04-22-2009BladactaniaQuote:

Just keep track of the last digit when multiplying with the next number. Then of the result get the last digit again.

Quote:

Just keep track of the last *non-zero* digit when multiplying with the next number. Then of the result get the last *non-zero* digit again.

- 04-22-2009matsp
I think the idea is that you multiply your numbers, and check if the last digit is zero - if it is, then divide the number by 10 to remove the last digit. Presumably, we then end up with a number that has only digits in it. It's still a bit troublesome that 10! is 36288 (plus 2 zeros), and 100! is 9.x E157, so there may be many more digits than the number of digits in long integer. Not sure about that.

--

Mats - 04-22-2009Tanuj_Tanmay
//I finally did it....couldn't check for "fairly large numbers"....but it works...

Code:`#include<stdio.h>`

int lastNonZero(int n);

int main()

{

int number,lastNonZeroDigit;

int i;

printf("Enter an integer:");

scanf("%d",&number);

lastNonZeroDigit = lastNonZero(number);

for(i=number-1 ; i>1 ; i--)

lastNonZeroDigit = lastNonZero(lastNonZeroDigit * i);

printf("The last Non Zero Digit in %d! = %d.\n",number,lastNonZeroDigit);

}

int lastNonZero(int n) //functn to calculate last non zero digit of 'n'

{

if(n%10 != 0)

return n%10;

else

return lastNonZero(n/10);

}

- 04-22-2009Bladactania
Good call on using recursion...

To check for numbers "too large" you could simply decide an arbitrary maximum number you accept from the user and add a simple if statement. However, since you're not actually calculating the factorial of the numbers, any number entered that is within the boundaries of the int type should still be ok. - 04-22-2009Snafuist
Now that you have a solution, let me explain my initial suggestion: the number of trailing zeros in n! depends on the multiplicity of the prime factor 5 in n!, as 2*5==10 and there are always more 2s than 5s in n! (in a contiguous progression of integers, 1/i-th of the elements is divisible by i). Hence, if you divide by 2^i instead of multiplying with 5^i (i.e. if you remove i factors of 2 instead of adding i factors of 5) while computing n!, you end up with n! without the trailing zeros.

Thus, the following pseudocode should compute the last digit of n!

Code:`for(k = 2; k <= n; k++)`

if(k == 5^i for some integer i)

fac = fac / 2^i; // for each 5, remove one 2

else

fac = fac * k;

last_digit_of_n_factorial = fac % 10;

Greets,

Philip - 04-22-2009Bladactania
I think it's interesting that you thought that was "obvious."

- 04-22-2009matsp
I'm just sort of thinking that if we have a number consisting of a number of digits ending with X and another number ending with Y, then the last digit is X * Y % 10 - I haven't tested it, but I think it's always true that nnnnX * mmmmY is the same final digit as X * Y. I did a few samples and it seems to work.

--

Mats - 04-22-2009Tanuj_Tanmay
thanx Philip...nice work...

u had completely different logic.....

its always nice to know different methods to solve a particular problem.. - 04-22-2009Tanuj_Tanmay
@matsp...kernel hacker...

you got it...that was the logic i used... - 04-22-2009SnafuistQuote:

I'm just sort of thinking that if we have a number consisting of a number of digits ending with X and another number ending with Y, then the last digit is X * Y % 10 - I haven't tested it, but I think it's always true that nnnnX * mmmmY is the same final digit as X * Y. I did a few samples and it seems to work.

Consider X=ab and Y=cd. Then X*Y = ab*cd = ab*c0 + ab*d (e.g. 17*23==17*20+17*3). Now, ab*c0 ends in a zero, so the last digit of X*Y is the same as the last digit of ab*d, which equals a0*d + b*d. But a0*d ends in zero again, so the last digit of X*Y must be the last digit of b*d.

Now you can either use induction over the number of digits in X and Y to show that this holds true for X,Y > 99, or you can have a simple argument involving the decimal representation of a number being a sum of powers of 10, which is easy to understand but too difficult to explain here because of notation (Sigma, variable subscripts, etc.)

If you're interested in the full proof (three lines in LaTeX), I may hack it up for you.

Greets,

Philip