## Last Non-zero Digit of Factorial

If you are not familiar with factorial read this.

**Question: Find the last non-zero digit of n!**

*Approach 1*

If you think you can calculate the factorial first and then divide out all the zeroes, you can but only to a certain extent, i mean to the point you can calculate n factorial. What if you had to find the last non-zero digit of a very large number whose factorial you cannot calculate.

*Approach 2*

This is the most popular technique and quite handy too. We know that n! = 1 x 2 x 3 …x (n-1) x n

or n! = (2^a2)(3^a3)(5^a5)(7^a7)…

or n! = (2^a2)(5^a5)(3^a3)(7^a7)…

Now we know that the number of zeroes in n1 is equal to a5. So n! divided by 10^a5 will be equal to factorial without trailing digits. Lets call this n! without trailing zeroes as (n!)’ .So,

(n!)’ = (2^(a2-a5))(3^a3)(7^a7)…

Let L(k) denote the least significant non-zero decimal digit of the integer k. So from above we can infer that

L(n!) = L((n!)’) = L[(2^(a2-a5))(3^a3)(7^a7)…]

= L[(3^a3)(7^a7)…]*L[(2^(a2-a5))]

This logic is implemented in the C/C++ function below.

int last_digit_factorial(int N) { int i,j,ans=1,a2=0,a5=0,a; for (i = 1; i <= N; i++) { j = i; //divide i by 2 and 5 while (j%2==0) { j /= 2; a2++; } while (j%5==0) { j/=5; a5++; } ans = (ans*(j%10))%10; } a=a2-a5; for (i = 1; i <= a; i++) ans=(ans * 2) %10; return ans; }

*Approach 3*

**Fact :**The powers of 2 3 7 and 1 have cyclic last digit.

So we divide all the primes into one of these groups and then take out the power accordingly.

power1[4]={1, 1, 1, 1}

power2[4]={6, 2, 4, 8}

power3[4]={1, 3, 9, 7}

power7[4]={1, 7, 9, 3}

power9[4]={1, 9, 1, 9}

So for example, if we have to find last digit in 6!

6! = 1 * 2 * 3 * 4 * 5 * 6

6! = 2^3 * (3^2) * 10

6!’ = 2^3 * (3^2)

We know the power of 3 has cyclic last digit, so 3^2 last digit is 9 or power3[2 mod 4]

L(6!) = L(6!’) = power2[3 mod 4] * power3[2 mod 4] mod 10

= 32 mod 10 = 2

But why code this method when we have a simpler approach.

*Approach 4*

** Theory : **Since we know that only a factor 5 brings in zero and we always have more powers of 2 than of 5, so the value of L(n!) is easily computed recursively as L(L(n)L((n-1)!)) unless n is a multiple of 5, in which case we need more information. As a result, the values of L(n!) come in fixed strings of five, as shown below :

1 | 5 | 10 | 15 | 20 | 25 | |

L(n!) | 1264 | 22428 | 88682 | 88682 | 44846 | 44846 |

Thus if we know any value of 5n we can get the value of 5n+j. For example if we know value of L(15!) we know the value of L(16!), L(17!) up-to L(19!). But how to get the value of 5n. If we map the starting values of the L(5n!) we get like 2 8 8 4 4 8 2 2 6. They come in another fixed strings of five. So we need to know L(25n!) to know L((25n+5j)!) for j = 0,1,2,3,4. Continuing in this way if we tabulate the values of L((5^t n)!) we get :

L(n!) | 1264 | 22428 | 88682 | 88682 | 44846 | 44846 |

L(5n!) | 2884 | 48226 | 24668 | 48226 | 48226 | 86442 |

L(25n!) | 4244 | 82622 | 82622 | 28488 | 46866 | 64244 |

L(125n!) | 8824 | 68824 | 26648 | 68824 | 42286 | 26648 |

L(625n!) | 1264 | 22428 | 88682 | 88682 | 44846 | 44846 |

So we see that the pattern for L(625n!) is same as L(n!). Hence we can conclude that the pattern for L((5^j n)!) is the same as for L((5^(j+4) n)!). So we can use a modulo 4 function to get the next results. Also we can see below that each of the four row have a starting digit as 0 , 2 , 4, 6 and 8.

*Result : *

k mod 4 | |||||

0 | 06264 | 22428 | 44846 | 66264 | 88682 |

1 | 02884 | 24668 | 48226 | 62884 | 86442 |

2 | 04244 | 28488 | 46866 | 64244 | 82622 |

3 | 08824 | 26648 | 42286 | 68824 | 84462 |

This is all we need to get the last digit of n! or L(n!). First we convert the given number n into base 5. So we have

n = d_0 + d_1*5 + d_2*5^2 + … + d_h*5^h

where d_0 is the least significant digit.

Now we enter the above table at the row h (mod 4) in the block whose first digit is 0 (because the coefficient of 5^(h+1) is zero), and determine the digit in the (d_h)th position of this block. Let this digit be denoted by s_h. Then we enter the table at row h-1 (mod 4) in the block that begins with s_h, and determine the digit in the (d_(h-1))th position of this block. Let this digit be denote by s_(h-1). We continue in this way down to s_0, which is the least significant non-zero digit of n!.

*Example : *

To illustrate, consider the case of the decimal number n=1592. In the base 5 this is n=22332. Now we enter the above table at row k=4=0 (mod 4) in the block beginning with 0, which is 06264. The leading digit of n (in the base 5) is 2, so we check the digit in position 2 of this block to give L((2*5^4)!) = 2. Then we enter the table at row k=3 (mod 4) in the block beginning with 2, which is 26648, to find L((2*5^4 + 2*5^3)!) = 6.

Then in the row k=2 (mod 4), the block beginning with 6 is 64244, and we find L((2*5^4 + 2*5^3 + 3*5^2)!) = 4. From this we know we’re in the block 48226 in row k=1 (mod 4), so we have L((2*5^4 + 2*5^3 + 3*5^2 + 3*5)!) = 2. Finally, we enter the row k=0 (mod 4) in block 22428 to find the result

L(1592!) = L((2*5^4 + 2*5^3 + 3*5^2 + 3*5 + 2)!) = 4

**Thus if there are k digits in the base 5 representation of n then we only need k lookups in the table to get the last non-zero digit.** Finally a C++ program for the algorithm :

#include using namespace std; int A[4][5][5] = { {0,6,2,6,4,2,2,4,2,8,4,4,8,4,6,6,6,2,6,4,8,8,6,8,2}, {0,2,8,8,4,2,4,6,6,8,4,8,2,2,6,6,2,8,8,4,8,6,4,4,2}, {0,4,2,4,4,2,8,4,8,8,4,6,8,6,6,6,4,2,4,4,8,2,6,2,2}, {0,8,8,2,4,2,6,6,4,8,4,2,2,8,6,6,8,8,2,4,8,4,4,6,2} }; char num[200]; char* dto5(int n) { int b=5; int j,l; register int i=0; do { j=n%b; num[i++]=(j<10) ? (j+'0'): ('A'+j-10); }while((n/=b)!=0); num[i]=''; l=strlen(num); reverse(num,num+l); return num; } int last_digit_factorial(int N) { char *num=dto5(N); int l = strlen(num),s=0,i; for (i=0;i<l;i++) { s=A[(l-1-i)%4][s/2][num[i]-'0']; } return s; } int main() { int N; while (scanf("%d", &N) == 1) { printf("%d\n", last_digit_factorial(N)); } return 0; }

**Can we make it even simpler. Yes.**

Let’s write n as 5k + r

So,

(n)! = (5k + r)!

= 1·2·3…k.(k+1)…(5k-1)·(5k)·(5k+1)…(5k+r)

(Seperating out multiples of 5)

= {5·10·15…(5k)} · {1·2·3·4·6·7…(5k-4)·(5k-3)·(5k-2)·(5k-1)·(5k+1)…(5k+r)}

(Expanding multiples of 5)

= {5·(2·5)·(3·5)…(k·5)} · {1·2·3·4·6·7…(5k-4)·(5k-3)·(5k-2)·(5k-1)·(5k+1)…(5k+r)}

= 5^k {1·2·3…k} · {1·2·3·4·6·7…(5k-4)·(5k-3)·(5k-2)·(5k-1)·(5k+1)…(5k+r)}

= 5^k · k! · {1·2·3·4·6·7…(5k-4)·(5k-3)·(5k-2)·(5k-1)·(5k+1)…(5k+r)}

= 5^k · k! · product{(5·i+1)·(5·i+2)·(5·i+3)·(5·i+4), i = 0 to k – 1} · (5k+1)…(5k+r)

(Multiplying and dividing by 2^k)

= 5^k · 2^k · k! · product((5i+1)·(5i+2)·(5i+3)·(5i+4)/2, i = 0 to k – 1) · (5k+1)…(5k+r)

= 10^k · k! · product((5i+1)·(5i+2)·(5i+3)·(5i+4)/2, i = 0 to k – 1) · (5k+1)…(5k+r)

Now to find the last digit of n! or L(n), we remove the power of 10 first and move to next type.

So,

L(n) = L(5k+r)

L(n) = L(k! · product((5i+1)·(5i+2)·(5i+3)·(5i+4)/2, i = 0 to k – 1))

L(n) = [L(k) · {product((5i+1)·(5i+2)·(5i+3)·(5i+4)/2, i = 0 to k – 1) mod 10} · {(5k+1)…(5k+r) mod 10 }] mod 10

Now let us first find P = (5i+1)·(5i+2)·(5i+3)·(5i+4)/2 mod 10

To calculate this we will have to take (mod 2) value and (mod 5) value and then using chinese remainder take out (mod 10) value.

Clearly P mod 2 = 0.

Modular inverse of 2 (mod 5) is 3.

So,

P mod 5 = 1·2·3·4·3 mod 5

= 72 mod 5

= 2 mod 5

Using the chinese remainder theorem we get,

P mod 10 = 2 mod 10

Hence,

L(n) = [L(k) · {product((5i+1)·(5i+2)·(5i+3)·(5i+4)/2, i = 0 to k – 1) mod 10} · {(5k+1)…(5k+r) mod 10 }] mod 10

= [L(k) · {product(2, i = 0 to k – 1) mod 10} · L(r)] mod 10

= [L(k) · L(r) · {2^k mod 10}] mod 10

= 2^k · L(k) · L(r) mod 10

Also,

2^k mod 10 = 1 when k = 6 when k = 4i

= 2 when k = 4i+1

= 4 when k = 4i+2

= 8 when k = 4i+3

Hence,

L(0) = L(1) = 1

L(2) = 2

L(3) = 6

L(4) = 4

L(n) = L(5k+r) = 2^k·L(k)·L(r) (mod 10)

And here’s a simpler code.

#include<iostream> using namespace std; int P(int K) { int A[]={6,2,4,8}; if (K<1) return 1; return A[K%4]; } int L(int N) { int A[]={1,1,2,6,4}; if (N<5) return A[N]; return (P(N/5)*L(N/5)*L(N%5))%10; } int main() { int N; while (scanf("%d", &N) == 1) printf("%d\n", L(N)); return 0; }

NJOY!!!

fR0D

I found the post very useful. . .

Thanks a lot. . .

Hope that a lot of such important posts will be come on later:-). . .

MuhammedJune 28, 2009 at 3:32 PM

how about finding last k nonzero digits of factorial??

boySeptember 26, 2009 at 2:58 PM

Nice !

But what is this ? : num[i]=”

Besides I think readers will find this link interesting :http://ipsc.ksp.sk/contests/ipsc1999/real/solutions/d.php 🙂

nthrgeekDecember 24, 2009 at 8:01 PM

Actually the dto5 function was a general code to convert from decimal to any base. So the num[i] = ‘ ‘ .

fR0DDYDecember 25, 2009 at 1:20 PM

very very useful.. helped me to get around the soln of spoj prob..

thanks alot….

keep it up

pushkarAugust 1, 2010 at 10:45 AM

Hey buddy,

Thanks for sharing a good information. I appreciate.

Thanks

ranganathgAugust 10, 2010 at 10:46 PM

[…] factorial — The Endeavour posted at The Endeavour. Which naturally leads to Gaurav Kumar‘s Last Non-zero Digit of Factorial posted at COME ON CODE […]

Carnival of Mathematics 69 « JD2718September 3, 2010 at 9:04 PM

but why would anyone wanna find the last non-zero digit of a factorial??? where is this applied for good use?

brainOctober 1, 2010 at 12:37 PM

awesome..!!

kushDecember 15, 2010 at 6:34 PM

This is a solution to the Math Monthly problem 11568 (in the April, 2011 issue).

EMRApril 12, 2011 at 7:22 PM

[…] ] . After searching a bit , i found couple of links which are quite good and self explanatory 1] comeoncode 2] mathproblem 3] mathpages [ this one contains other nice problems also ] . I implemented the […]

Last Non zero digit of factorial « My WeblogMay 24, 2011 at 2:39 AM

comeoncodeon is a very helpful site, the way of explanation is great.

chetanJune 4, 2011 at 4:27 AM

great explanation…………….

praneethJune 7, 2011 at 5:03 PM

So n! divided by 10^a5 will be equal to factorial without trailing digits. Lets call this n! without trailing zeroes as (n!)’

this statement isn’t right it is divisible by 10^min(a5,a2)

TDLJuly 11, 2011 at 12:53 AM

Hi TDL,

It is correct, since min(a5,a2) is always equal to a5.

fR0DDYJuly 11, 2011 at 9:46 PM

wat is L(n!)

fdgNovember 15, 2011 at 11:48 AM

It is the last non-zero digit of n factorial.

fR0DDYNovember 15, 2011 at 11:57 AM

[…] 한 자리만 구해도 된다면, 훨씬 빠른 방법이 있습니다. Last Non-zero Digit of Factorial을 읽어 […]

코딩 인터뷰 완전 분석 210쪽 17.3 변형 문제 풀이 | dlimpid's blogSeptember 5, 2012 at 4:19 PM

Really great. I didn’t come up a close form solution, through it’s a logN algorithm too.

XiaoyiNovember 13, 2012 at 8:58 PM

could you explain why {(5k+1)…(5k+r) mod 10 } = L(r)? As it only stand when k is even.

XiaoyiNovember 13, 2012 at 10:49 PM

Aha, (2(5k+1)(5k+2)…(5k+r)) mod 10 = 2 * L(r).

XiaoyiNovember 13, 2012 at 11:06 PM

i dont understand that chinese remainder theorem part…i mean how to know the result of P mod 10 from P mod 2 and P and 5….??..can u pls explain…

jayanthFebruary 1, 2013 at 6:42 AM

Probably this will help: http://en.wikipedia.org/wiki/Chinese_remainder_theorem

fR0DDYFebruary 1, 2013 at 6:44 AM

thanks….or alternatively we can find P mod 10 in the foll way right…??

we know that [(5i+1)(5i+1)(5i+1)(5i+4)] mod 10 will always give 4…but P is (5i+1)(5i+1)(5i+1)(5i+4)/2….P mod 10 is (4/2)%10 which is (2)mod10 that is equal to 2….and now this gets repeated k times….therefore P mod 10 is nothing but (2^k)mod10…..

and btw amazing post with gr8 explanation….thanks…:)

jayanthFebruary 5, 2013 at 9:45 PM

sorry i meant (5i+1)(5i+2)(5i+3)(5i+4)…..not (5i+1)(5i+1)(5i+1)(5i+4)…

jayanthFebruary 5, 2013 at 9:51 PM

[…] musiałem się poddać. Aż w końcu trafiłem na blog fR0DDY’ego, który tłumaczy wszystko jak krowie na rowie. Hmm czyli coś dla mnie. Zaznaczyć trzeba, że […]

Ostatnia niezerowa cyfra silni | NitcodeFebruary 27, 2015 at 5:00 PM