COME ON CODE ON

A blog about programming and more programming.

Last Non-zero Digit of Factorial

with 25 comments

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

About these ads

Written by fR0DDY

June 20, 2009 at 6:12 PM

Posted in Programming

Tagged with , , , , , ,

25 Responses

Subscribe to comments with RSS.

  1. I found the post very useful. . .
    Thanks a lot. . .
    Hope that a lot of such important posts will be come on later:-). . .

    Muhammed

    June 28, 2009 at 3:32 PM

  2. how about finding last k nonzero digits of factorial??

    boy

    September 26, 2009 at 2:58 PM

  3. 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 :-)

    nthrgeek

    December 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] = ‘ ‘ .

      fR0DDY

      December 25, 2009 at 1:20 PM

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

    thanks alot….

    keep it up

    pushkar

    August 1, 2010 at 10:45 AM

  5. Hey buddy,

    Thanks for sharing a good information. I appreciate.

    Thanks

    ranganathg

    August 10, 2010 at 10:46 PM

  6. [...] 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 [...]

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

    brain

    October 1, 2010 at 12:37 PM

  8. awesome..!!

    kush

    December 15, 2010 at 6:34 PM

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

    EMR

    April 12, 2011 at 7:22 PM

  10. [...] ] . 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 [...]

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

    chetan

    June 4, 2011 at 4:27 AM

  12. great explanation…………….

    praneeth

    June 7, 2011 at 5:03 PM

  13. 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)

    TDL

    July 11, 2011 at 12:53 AM

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

      fR0DDY

      July 11, 2011 at 9:46 PM

  14. wat is L(n!)

    fdg

    November 15, 2011 at 11:48 AM

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

      fR0DDY

      November 15, 2011 at 11:57 AM

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

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

    Xiaoyi

    November 13, 2012 at 8:58 PM

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

    Xiaoyi

    November 13, 2012 at 10:49 PM

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

      Xiaoyi

      November 13, 2012 at 11:06 PM

  18. 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…

    jayanth

    February 1, 2013 at 6:42 AM

    • fR0DDY

      February 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…:)

        jayanth

        February 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)…

        jayanth

        February 5, 2013 at 9:51 PM


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 230 other followers

%d bloggers like this: