Finding last non zero digit of a factorial

We know that finding the factorial of large numbers is not possible with available data types in C++.We can also see that there are trailing zeros in every factorial after 5!. It is an interesting question that what will be the last non-zero digit of the factorial of a number.

Here is a simple algorithm based on recurrence relation by which we can easily find the last nonzero digit of a factorial.
Let's say D(N) denotes the last non-zero digit of factorial, then the algorithm says

D(N)=4*D[N/5]*D(Unit digit of N)[If tens digit of N is odd]
D(N)=6*D[N/5]*D(Unit digit of N)[If tens digit of N is even]; Where [N/5]

is greatest Integer Function.
for the numbers less than 10 we can easily find the last non-zero digit by multiplying.
D(1)=1 D(2)=2 D(3)=6 D(4)=4 D(5)=2 D(6)=2 D(7)=4 D(8)=2 D(9)=8

Example- 
What will be the last non-zero digit of 26!*33!.
D(26)=6*D[26/5]*D(6)=6*D(5)*D(6)=6*2*2=4
[D(5) means last non zero digit of 5!=120 which is 2, same for D(6)]
D(33)=4*D[33/5]*D(3)=4*D(6)*D(3)=4*2*6=8
So the last non-zero digit of 26!*33! will be=4*8=32 (So the answer is 2)


//Below is the c++ implementation of this algorithm-




#include<bits/stdc++.h>
using namespace std;
//initialize the values of last non-zero digit of numbers from 0-9
int Dig[]={1,1,2,6,4,2,2,4,2,8};
int digit(int N)
{
    int D;
    if(N<10)
    return Dig[N];
    //check whether ten digit is odd or even
        //if N=335 So N/10=33 and (N/10)%10=3
        //if it is even solve the recurrance relation for even  
    if(((N/10)%10)%2==0)
        D=6*digit(floor(N/5))*Dig[N%10];
    ////if it is even solve the recurrance relation for even
    else
            D=4*digit(floor(N/5))*Dig[N%10];
            printf("%d\n",D);
    return D;
}
int main()
{
    int N,D;
    cout<<"Enter the number:";
    cin>>N;
    D=digit(N);
    printf("last non zero digit=%d",D%10);
return 0;
}
OUTPUT- Enter the number:26 last non-zero digit=8






Comments :

Post a Comment