I need an efficient program to print last non zero digit of n!...n can be fairly large number
I need an efficient program to print last non zero digit of n!...n can be fairly large number
How large is "fairly large"?
--
Mats
Compilers can produce warnings - make the compiler programmers happy: Use them!
Please don't PM me for help - and no, I don't do help over instant messengers.
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.
Last edited by Snafuist; 04-22-2009 at 07:25 AM.
All things begin as source code.
Source code begins with an empty file.
-- Tao Te Chip
should beJust keep track of the last digit when multiplying with the next number. Then of the result get the last digit again.
If you just keep the last digit, once that last digit becomes 0 then it will forever remain 0.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.
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
Compilers can produce warnings - make the compiler programmers happy: Use them!
Please don't PM me for help - and no, I don't do help over instant messengers.
//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); }
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.
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!
It's easy to fill in actual code for the if condition. Note that this solution also works for arbitrarily large 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
All things begin as source code.
Source code begins with an empty file.
-- Tao Te Chip
I think it's interesting that you thought that was "obvious."
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
Compilers can produce warnings - make the compiler programmers happy: Use them!
Please don't PM me for help - and no, I don't do help over instant messengers.
thanx Philip...nice work...
u had completely different logic.....
its always nice to know different methods to solve a particular problem..
@matsp...kernel hacker...
you got it...that was the logic i used...
Oh, I thought that was clear.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
All things begin as source code.
Source code begins with an empty file.
-- Tao Te Chip