## 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 readInt :: BS.ByteString -> Integer readInt x = case BS.readInteger x of 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.

Advertisements

No comments yet.

## Leave a Reply