COME ON CODE ON

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 :

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 :

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 :

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