Program to print last non zero digit of n!

This is a discussion on Program to print last non zero digit of n! within the C Programming forums, part of the General Programming Boards category; I need an efficient program to print last non zero digit of n!...n can be fairly large number...

  1. #1
    Registered User Tanuj_Tanmay's Avatar
    Join Date
    Feb 2009
    Location
    &CProgramming
    Posts
    12

    Thumbs up Program 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

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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.

  3. #3
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Quote Originally Posted by Tanuj_Tanmay View Post
    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.
    Last edited by Snafuist; 04-22-2009 at 08:25 AM.
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  4. #4
    Registered User Tanuj_Tanmay's Avatar
    Join Date
    Feb 2009
    Location
    &CProgramming
    Posts
    12
    Quote Originally Posted by matsp View Post
    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..

  5. #5
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by Tanuj_Tanmay View Post
    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?

  6. #6
    Registered User
    Join Date
    Feb 2009
    Posts
    278
    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.

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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.

  8. #8
    Registered User Tanuj_Tanmay's Avatar
    Join Date
    Feb 2009
    Location
    &CProgramming
    Posts
    12
    //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);
    }

  9. #9
    Registered User
    Join Date
    Feb 2009
    Posts
    278
    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.

  10. #10
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    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;
    It's easy to fill in actual code for the if condition. Note that this solution also works for arbitrarily large n.

    Greets,
    Philip
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  11. #11
    Registered User
    Join Date
    Feb 2009
    Posts
    278
    I think it's interesting that you thought that was "obvious."

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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.

  13. #13
    Registered User Tanuj_Tanmay's Avatar
    Join Date
    Feb 2009
    Location
    &CProgramming
    Posts
    12
    thanx Philip...nice work...
    u had completely different logic.....
    its always nice to know different methods to solve a particular problem..

  14. #14
    Registered User Tanuj_Tanmay's Avatar
    Join Date
    Feb 2009
    Location
    &CProgramming
    Posts
    12
    @matsp...kernel hacker...
    you got it...that was the logic i used...

  15. #15
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    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
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Personal Program that is making me go wtf?
    By Submeg in forum C Programming
    Replies: 20
    Last Post: 06-27-2006, 01:13 AM
  2. How to complete program. Any probs now?
    By stehigs321 in forum C Programming
    Replies: 7
    Last Post: 11-19-2003, 04:03 PM
  3. My program, anyhelp
    By @licomb in forum C Programming
    Replies: 14
    Last Post: 08-14-2001, 11:04 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21