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.
D(N)=4*D[N/5]*D(Unit digit of N)[If tens digit of N is odd]OUTPUT- Enter the number:26 last non-zero digit=8
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!.
#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;
}
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(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)
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;
}
Comments :
Post a Comment