My Weblog

Blog about programming and math

SPOJ 2124. Last Non-Zero Digit of Factorials

SPOJ 2124. Last Non-Zero Digit of Factorials finally solved . I used the formula given on OEIS. Convert the number on base 5. n = a_0 + 5 a_1 + 5^2 a_2 + ... +5^N a_N (the expansion of n in base-5)then last digit will be 6*\prod_{i=0}^N (a_i)! (2^{i a_i})  mod 10 . Accepted Haskell code.

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

convertBase :: Integer -> [Integer]
convertBase 0 = []
convertBase n = (mod n  5)  : convertBase ( div n 5 ) 



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 n =  mod ( 6*fst a ) 10 where 
  	a = foldl (\(acc , i ) x -> ( mod  ( acc *  product [1..x] * 2^(i*x) ) 10 , i + 1 ) ) ( 1 , 0 ) $ convertBase n 


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

June 17, 2011 - Posted by | Programming | , ,

No comments yet.

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

%d bloggers like this: