# My Weblog

## Last Non zero digit of factorial

Today i found a problem on spoj which asks for finding last non zero digit of factorial of large number [ 10 ^100 ] . 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 algorithm given on first two links and got TLE but worth sharing this code because today i learned how to use Byte-String instead of String which is quite slower in Haskell. You may check SPOJ section on Haskell Wiki.

```import Data.List
import qualified Data.ByteString.Char8 as BS

helpMod::Integer->Integer->Integer->Integer
helpMod a d n= fun a d where
fun a 1 = mod a n
fun a 2 = mod (a^2) n
fun a d = let
p=fun (mod (a^2) n) (div d 2)
q=if odd d then mod (a*p) n else p
in mod q n

Just ( i , _ ) -> i
Nothing -> error " upseperable ints "

solve ::Integer -> Integer
solve 0 = 1
solve 1 = 1
solve 2 = 2
solve 3 = 6
solve 4 = 4
solve n = mod ( ( helpMod 2 q 10 ) * ( solve q ) *( solve r ) )  10 where
( q , r ) = quotRem n 5

main = BS.interact \$ BS.unlines. map ( BS.pack . show . solve )  . map readInt. BS.lines
```

Looking forward to implement mathpages algorithm in Haskell.