Program to print last non zero digit of n!

[Tanuj_Tanmay]

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

[matsp]

How large is "fairly large"?

--
Mats

[Snafuist]

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

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.

[Tanuj_Tanmay]

How large is "fairly large"?

--
Mats

the number can be 100....factorial of which is impossible for me to find....but my program sud give correct output to it...without actually calculating its factorial..

[EVOEx]

the number can be 100....factorial of which is impossible for me to find....but my program sud give correct output to it...without actually calculating its factorial..

That shouldn't be too tough, with "only" 100. Just keep track of the last digit when multiplying with the next number. Then of the result get the last digit again.

What do you have so far then?

[Bladactania]

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

should be

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.

If you just keep the last digit, once that last digit becomes 0 then it will forever remain 0.

[matsp]

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

[Tanuj_Tanmay]

//I finally did it....couldn't check for "fairly large numbers"....but it works...

#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);
}

[Bladactania]

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.

[Snafuist]

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!

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;

It's easy to fill in actual code for the if condition. Note that this solution also works for arbitrarily large n.

Greets,
Philip

[Bladactania]

I think it's interesting that you thought that was "obvious."

[matsp]

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

[Tanuj_Tanmay]

thanx Philip...nice work...
u had completely different logic.....
its always nice to know different methods to solve a particular problem..

[Tanuj_Tanmay]

@matsp...kernel hacker...
you got it...that was the logic i used...

[Snafuist]

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.

Oh, I thought that was clear.

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