Number of Distinct LCS

This problem appeared in the November edition of CodeChef Monthly Contest. The problem is to find the number of distinct LCS that can be formed from the given two strings. A nice tutorial about it is given on the CodeChef site itself. Also there is a research paper available here. Here’s my solution to the CodeChef problem.

#include<iostream>
using namespace std;

int L[1005][1005];
int D[1005][1005];

int LCS(string X,string Y)
{
     int m = X.length(),n=Y.length();

     int i,j;
     for (i=0;i<=m;i++)
     {
         for (j=0;j<=n;j++)
         {
             if (i==0 || j==0)
                L[i][j]=0;
             else
             {
                 if (X[i-1]==Y[j-1])
                    L[i][j]=L[i-1][j-1]+1;
                 else
                     L[i][j]=max(L[i][j-1],L[i-1][j]);
             }
         }
     }
     return (L[m][n]);
}

int NLCS(string X,string Y)
{
    int m = X.length(),n=Y.length();
    int i,j;
    for (i=0;i<=m;i++)
    {
        for (j=0;j<=n;j++)
        {
             if (i==0 || j==0)
                D[i][j]=1;
             else
             {
                 D[i][j]=0;
                 if (X[i-1]==Y[j-1])
                 {
                    D[i][j]=D[i-1][j-1];
                 }
                 else
                 {
                     if (L[i-1][j]==L[i][j])
                        D[i][j]=(D[i][j]+D[i-1][j])%23102009;
                     if (L[i][j-1]==L[i][j])
                        D[i][j]=(D[i][j]+D[i][j-1])%23102009;
                     if (L[i-1][j-1]==L[i][j])
                     {
                        if (D[i][j]<D[i-1][j-1])
                           D[i][j]+=23102009;
                        D[i][j]=(D[i][j]-D[i-1][j-1]);
                     }
                 }
             }
        }
     }
     return (D[m][n]);
}

int main()
{
    string X,Y;
    int T,A,B;
    scanf("%d",&T);
    while (T--)
    {
          cin>>X>>Y;
          A=LCS(X,Y);
          B=NLCS(X,Y);
          printf("%d %d\n",A,B);
    }
}

NJOY!
-fR0DDY

Binary Indexed Tree (BIT)

In this post we will discuss the Binary Indexed Trees structure. According to Peter M. Fenwick, this structure was first used for data compression. Let’s define the following problem: We have n boxes. Possible queries are

1. Add marble to box i
2. Return sum of marbles from box k to box l

The naive solution has time complexity of O(1) for query 1 and O(n) for query 2. Suppose we make m queries. The worst case (when all queries are 2) has time complexity O(n * m). Binary Indexed Trees are easy to code and have worst time complexity O(m log n).

The two major functions are

• update (idx,val) : increases the frequency of index idx with the value val
• read (idx) : reads the cumulative frequency of index idx

Note : tree[idx] is sum of frequencies from index (idx – 2^r + 1) to index idx where r is a position in idx of the last digit 1 (from left to right) in binary notation, f is frequency of index, c is cumulative frequency of index, tree is value stored in tree data structure.

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
f	1	0	2	1	1	3	0	4	2	5	2	2	3	1	0	2
c	1	1	3	4	5	8	8	12	14	19	21	23	26	27	27	29
tree	1	1	2	4	1	4	0	12	2	7	2	11	3	4	0	29

Table 1.1

 

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
tree	1	1..2	3	1..4	5	5..6	7	1..8	9	9..10	11	9..12	13	13..14	15	1..16

Table 1.2 – table of responsibility

Here’s a C++ template code :

#include<iostream>
using namespace std;

template<class T>
class BIT
{
      T *tree;
      int maxVal;
      public:
      BIT(int N)
      {
              tree = new T[N+1];
              memset(tree,0,sizeof tree);
              maxVal = N;
      }
      void update(int idx, T val)
      {
           while (idx <= maxVal)
           {
                 tree[idx] += val;
                 idx += (idx & -idx);
           }
      }
      //Returns the cumulative frequency of index idx
      T read(int idx)
      {
        T sum=0;
        while (idx>0)
        {
              sum += tree[idx];
              idx -= (idx & -idx);
        }
        return sum;
      }
};

int main()
{
    int a[100],cur=1,mul=2,add=19,MAX=65536,x,i;
    //Initialize the size by the
    //maximum value the tree can have
    BIT<int> B(MAX);
    for (i=0;i<50;i++)
    {
        a[i] = cur;
        B.update(a[i],1);
        cur = ((cur * mul + add) % MAX);
    }
    while (cin>>x)
    {
          cout<<B.read(x)<<endl;
    }

}

NJOY!
-fR0D

Segment Trees

A segment tree is a heap-like data structure that can be used for making update/query operations upon array intervals in logarithmical time. We define the segment tree for the interval [i, j] in the following recursive manner:

• the first node will hold the information for the interval [i, j]
• if i<j the left and right son will hold the information for the intervals [i, (i+j)/2] and [(i+j)/2+1, j]

See the picture below to understand more :

Segment Tree

We can use segment trees to solve Range Minimum/Maximum Query Problems (RMQ). The time complexity is T(N, log N) where O(N) is the time required to build the tree and each query takes O(log N) time. Here’s a C++ template implementation :

#include<iostream>
using namespace std;
#include<math.h>

template<class T>
class SegmentTree
{
     int *A,size;
     public:
     SegmentTree(int N)
     {
          int x = (int)(ceil(log(N)))+1;
          size = 2*(int)pow(2,x);
          A = new int[size];
          memset(A,-1,sizeof(A));
     }
     void initialize(int node, int start,
                         int end, T *array)
     {

          if (start==end)
             A[node] = start;
          else
          {
              int mid = (start+end)/2;
              initialize(2*node,start,mid,array);
              initialize(2*node+1,mid+1,end,array);
              if (array[A[2*node]]<=
                     array[A[2*node+1]])
                 A[node] = A[2 * node];
              else
                  A[node] = A[2 * node + 1];
          }
     }
     int query(int node, int start,
                   int end, int i, int j, T *array)
     {
         int id1,id2;
         if (i>end || j<start)
            return -1;

         if (start>=i && end<=j)
            return A[node];

         int mid = (start+end)/2;
         id1 = query(2*node,start,mid,i,j,array);
         id2 = query(2*node+1,mid+1,end,i,j,array);

         if (id1==-1)
            return A[node] = id2;
         if (id2==-1)
            return A[node] = id1;

         if (array[id1]<=array[id2])
            return A[node] = id1;
         else
             return A[node] = id2;
     }
};

int main()
{
    int i,j,N;
    int A[1000];
    scanf("%d",&N);
    for (i=0;i<N;i++)
        scanf("%d",&A[i]);

    SegmentTree<int> s(N);
    s.initialize(1,0,N-1,A);
    while (scanf("%d%d",&i,&j)!=EOF)
      printf("%d\n",A[s.query(1,0,N-1,i-1,j-1,A)]);
}

NJOY!
-fR0D

Subsequence Frequency

The question is to find the number of times a string appears as a subsequence in an another string. A similar question was asked in Google Code Jam 09. Here is the link.

So how do we do it. If you think the general way the first brute force method which comes to mind is to get a matrix for the general subsequence problem and then backtrack all paths that lead to the subsequence. But the backtracking will be too time consuming. Now the second thought which comes to mind is can’t we have a similar dynamic programming approach to find the frequency rather than length. Yes, thankfully we can do that. How?

First lets start with a string of two letters. Suppose we need to find the occurence of ab in abbacb. We can calculate the answer to be four. How did we do it, there are three b’s after first ‘a’ and only one after the second ‘a’, all in all four. So if somehow we manipulate the table to deal with the frequency of characters we can take out the total numbers of times the string appears as subsequence. If you wan’t to try out the algorithm for yourself, now is the right time. What follows next is the algorithm.
We have the table for the above example as :

		a	b	b	a	c	b
	0	1	1	1	1	1	1
a	0	1	1	1	2	2	2
b	0	0	1	2	2	2	4

As seen above we set the row[0] values to 1 and column[0] values to 0. Here’s the algorithm.
Let’s call the string whose frequency is to be found as str1 and given string str2.

for i from 1 to length(str1)
{
    for j from 1 to length(str2)
    {
        if (str1[i-1]==str2[j-1])
           table[i][j]=table[i-1][j]+table[i][j-1];
        else
            table[i][j]=table[i][j-1];
    }
}

Here’s a C++ code for the Code Jam Question :

#include<iostream>
using namespace std;

char str[1000],cj[]="welcome to code jam";
int M[30][1000]={0};

int main()
{
    int t,i,j,k,l,lcj=strlen(cj);;
    scanf("%d\n",&t);
    for (j=1;j<=1000;j++)
        M[0][j]=1;
    for (j=1;j<=lcj;j++)
        M[j][0]=0;
    for (k=1;k<=t;k++)
    {
        gets(str);
        l=strlen(str);
        for (i=1;i<=lcj;i++)
        {
            M[i][0]=0;
            for (j=1;j<=l;j++)
                if (cj[i-1]==str[j-1])
                M[i][j]=(M[i-1][j]+M[i][j-1])%10000;
                else M[i][j]= M[i][j-1];
        }
        printf("Case #%d: %04d\n",k,M[lcj][l]);
    }
}

Happy Coding!
-fR0D

Longest Increasing Subsequence (LIS)

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous.
For example for the sequence -7 10 9 2 3 8 8 1 the longest (strictly) increasing subsequence is -7 2 3 8 of length 4.

There are few methods to solve this question. The very first method is to sort the given sequence and save it into another array and then take out the longest common subsequence of the two arrays. This method has a complexity of O(n²) which should be good for most question but not all.

We will see here an algorithm which take O(n log k) time where k is the size of the LIS. For explanation on this algorithm see Faster Algorithm on this page. Here’s a small code to calculate only the length of the LIS.

#include<iostream>
#include<set>
#include<vector>
using namespace std;

int LIS(vector<int> A)
{
    int N = A.size(),i;
    set<int> s;
    set<int>::iterator k;
    for (i=0;i<N;i++)
    {
        if (s.insert(A[i]).second)
        {
           k = s.find(A[i]);
           k++;
           if (k!=s.end())
              s.erase(k);
        }
    }
    return s.size();
}

To also get the LIS we need to maintain a previous array which stores the index of the previous element in the LIS. Here’s a C++ implementation. It returns the LIS as an array.

#include<iostream>
#include<map>
#include<vector>
using namespace std;

typedef pair < int , int > PI;

vector<int> LIS(vector<int> A)
{
    int N = A.size(),i,j=-1,t;
    vector<int> pre(N,-1),res;
    map<int,int> m;
    map<int,int>::iterator k,l;
    for (i=0;i<N;i++)
    {
        if (m.insert(PI(A[i],i)).second)
        {
           k = m.find(A[i]);
           l = k;
           k++;
           if (l==m.begin())
                  pre[i]=-1;
           else
           {
               l--;
               pre[i]=l->second;
           }
           if (k!=m.end())
              m.erase(k);
        }
    }
    k=m.end();
    k--;
    j = k->second;
    while (j!=-1)
    {
          res.push_back(A[j]);
          j = pre[j];
    }
    reverse (res.begin(),res.end());
    return res;
}

Note that if there are more than one LIS the above code prints the last one which occured in the input array. Also to get the LDS we just need to change the lines :

set<int> s;
to
set<int,greater<int> > s;
and
map<int,int> m;
to
map<int,int,greater<int> > m;

Also little changes need to be made to the above codes if you dont want the LIS to be strictly increasing and rather be Longest Non-Decreasing Subsequence or Longest Non-Increasing Subsequence.

Happy Coding!
-fR0D

Longest Common Subsequence (LCS)

The longest common subsequence (LCS) problem is to find the longest subsequence common to all sequences in a set of sequences (often just two).

First we look into only finding the length of LCS. We can easily construct an exponential time recursive algorithm to compute the length of the LCS. But using Dynamic Programming (DP) to compute the solution bottom up the same job can be done in O(mn) time where m and n are the lengths of the subsequences. Here is a C++ code to do so. Note that the code also uses very less space.

int LCS(string X,string Y)
{
     if (Y.length() > X.length())
        swap(X,Y);
     int m = X.length(),n=Y.length();
     vector< vector<int> > c(2, vector<int>(n+1,0));
     int i,j;
     for (i=1;i<=m;i++)
     {
         for (j=1;j<=n;j++)
         {
             if (X[i-1]==Y[j-1])
                c[1][j]=c[0][j-1]+1;
             else
                 c[1][j]=max(c[1][j-1],c[0][j]);
         }
    	 for (j=1;j<=n;j++)
    		 c[0][j]=c[1][j];
     }
     return (c[1][n]);
}

If we also wish to print the subsequence we use a space of size m x n to get the LCS. Here’s the code

string X,Y;
vector< vector<int> > c(101, vector<int>(101,0));
int m,n,ctr;

void LCS()
{
     m = X.length(),n=Y.length();

     int i,j;
     for (i=0;i<=m;i++)
         for (j=0;j<=n;j++)
             c[i][j]=0;

     for (i=1;i<=m;i++)
         for (j=1;j<=n;j++)
         {
             if (X[i-1]==Y[j-1])
                c[i][j]=c[i-1][j-1]+1;
             else
                 c[i][j]=max(c[i][j-1],c[i-1][j]);
         }
}

void printLCS(int i,int j)
{
    if (i==0 || j==0)
       return;
    if (c[i][j]==c[i-1][j-1]+1)
    {
       printLCS(i-1,j-1);
       cout<<X[i-1];
    }
    else if (c[i][j]==c[i-1][j])
         printLCS(i-1,j);
    else
        printLCS(i,j-1);
}

int main()
{
    while(cin>>X>>Y)
    {
        LCS();
        printLCS(m,n);
        cout<<endl ;
    }
}

This post is a prequel to posts on similar topics that i wish to write.

NJOY
-fR0D

Program without header file?

So continuing in the series of program without, here are two more programs. The first one is just a valid C program without any header file.

int main()
{
    return 0;
}

The above program will actually compile and run. But you will say it did nothing. So lets have a program without header file which prints something.

extern "C"
{
       int printf(const char *format,...);
}

int main()
{
    printf("Hello World");
    return 0;
}

The only unexplained feature is extern “C”. For more about it read this.

NJOY!
fR0D

Programs without semicolons?

Let’s have a little fun. First of all try to write a C code to print Hello World! without using semicolons. Here’s the answer in C

#include <stdio.h>
int main()
{
    if (printf("Hello World!\n")) {}
}

or if you are a hardcore C++ fan then

#include <iostream>
int main()
{
    if (std::cout << "Hello world!" << std::endl)
    {}
}

But the real gem is the following program. A program to find the factorial of a number.

#include<iostream>
int main(int n)
{
    if (std::cin>>n)
    {
        if (int f=1 )
        {
            while (n != 1)
            {
                if ( f = n * f )
                {
                   if (--n){}
                }
            }
            if(std::cout<<"fac = "<<f<<std::endl)
            {}
        }
        else
        {}
    }
}

Infact any C program can be converted a non-semicolon form.

NJOY!
-fR0D

Counting Problems

Problem 1: Given a set of n numbers a_i sum up to M, and any K ≤ M, whether there is a subset of the numbers such that they sum up to  K?

Also called the Subset Sum Problem, in this problem, the number of times we can use a particular number is limited i.e. we can use a number only once. This problem can be done in two ways
1> Binary Representation of Numbers and
2> DP

1> Using Binary Representation of Numbers
First lets discuss the common approach for iterating through all subsets of a set. Mathematics tells us that the total number of subsets of a set is 2ⁿ. THe easier way to do this is in any programmin language is to represent each element of a set by a single bit of the number. So for example, if we have 3 elements in a set then we have 8 subsets. or we can iterate from 0 to 7 to get all subsets as

Number	Binary Representation
0	000
1	001
2	010
3	011
4	100
5	101
6	110
7	111

So if we let 1 in the binary represent that the number is selected and 0 that the number is not selected, we actually have all the subsets of the set. We can use this approach to solve the above problem by iterating through all subsets and finding whether the sum is equal to the required sum. The point to be noted is that this approach is quite slow since for a worst case scenario we iterate through all the 2ⁿ cases. Also checking each bit takes time. Here’s a simple C++ implementation of the above logic. Below is a program which takes as input N numbers and M the required subset sum and outputs Yes if the subset sum M is possible and No otherwise.

int a[21];
int main()
{
    int t,N,M,i,j,k,sum;
    bool F;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&N,&M);
        for (i=0;i<N;i++)
            scanf("%d",&a[i]); 

        F=0;
        j=1<<N;
        for (i=1;i<j && F==0;i++)
        {
            sum=0;
            for (k=0;k<N;k++)
            {
                if ((i & (1<<k)) == (1<<k))
                   sum += a[k];
            }
            if (sum == M)
            {
                F=1;
                printf("Yes\n");
            }

        }
        if (F==0)
           printf("No\n");

    }
}

2> DP Approach
This is the other approach to solving this problem. This method takes into account that the possible sum’s after including a number, are all previous possible sum’s plus the new number. So we only check whether x-a_i is a possible sum, if yes x is also a possible sum. We iterate from M (maximum possible sum) to a_i because we cannot include a number twice. Here’s the C++ implementation of the above program using DP approach.

int m[30000],a[21];
int main()
{
    int t,N,M,i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&N,&M);
        for (i=0;i<N;i++)
            scanf("%d",&a[i]);
        for (i=0;i<=M;i++)
            m[i]=0;
       	m[0]=1;
        for(i=0; i<N; i++)
        	for(j=M; j>=a[i]; j--)
        		m[j] |= m[j-a[i]];
  		if (m[M])
  		   printf("Yes\n");
	   else
	       printf("No\n");
    }
}

Problem 2: Given that the a_i’s are unlimited i.e you can use the numbers in the subset as many times as you want find whether a particular sum M is possible and if possible how many ways are there to do it?

Also called the Counting Change Problem, this problem is a variation of the above problem and we just need to change the direction of the second loop in the above problem. Here’s a program to find the number of ways to change a amount of Rs. 100 using the coins and notes of RS. 1,2,5,10,20,50,100.

int main()
{
    int coin[7]={1,2,5,10,20,50,100},i,j,x,c;
    x=100;
    vector<long long> ways(x+1,0);
    ways[0]=1;
    for (i=0;i<100;i++)
    {
      c=coin[i];
      for (j=c;j<=x;j++)
          ways[j]+=ways[j-c];
    }
    cout<<ways[100]<<endl;
}

More variations of the above problem can be minimizing the number of elements required to get a particular sum.

Problem 3: Find the number of ways of writing a number as the sum of positive integers?

Also called the Partition Function P of n, it is denoted by P(n). For example,

5	5
	4+1
	3+2
	3+1+1
	2+2+1
	2+1+1+1
	1+1+1+1+1

Euler invented a generating function which gives rise to a recurrence equation in P(n),

Below is a program to calculate P(n). It can easily modified to include large numbers.

#include<iostream>
using namespace std;
#include<map>

map <int , long long> P;

long long Calculate_Pn(long long n)
{
  if (n < 0)
     return 0;

  long long Pn = P[n];

  if (Pn == 0)
  {
     long long k;
     for (k = 1; k <= n; k++)
     {
         // A little bit of recursion
         long long n1 = n - k * (3 * k - 1) / 2;
         long long n2 = n - k * (3 * k + 1) / 2; 

         long long Pn1 = Calculate_Pn(n1);
         long long Pn2 = Calculate_Pn(n2); 

         // elements are alternately added
         // and subtracted
         if (k % 2 == 1)
            Pn = Pn + Pn1 + Pn2;
         else
              Pn = Pn - Pn1 - Pn2;
    }
       P[n]=Pn;
  }
  return Pn;
}

int main()
{
    long long i;
    P[0]=1;
    while (scanf("%lld",&i)!=EOF)
          printf("%lld\n",Calculate_Pn(i));
}

Happy Coding!!!
-fR0D

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<iostream>
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;
}

You can change the above code to handle string if the input number is very large.

NJOY!!!
fR0D