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

Followers

Total Pageviews

Blog Archive

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"