All rights are reserved by Niteesh Kumar.. Theme images by Storman. Powered by Blogger.

Followers

Total Pageviews

Blog Archive

Follow by Email

Translate

Sunday, 22 January 2017

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






0 on: "Finding last non zero digit of a factorial"