## SPOJ 10186. Divisor Digits

SPOJ 10186. Divisor Digits is easy problem in my opinion but I haven’t solve this problem so I may be wrong and read it further at you own risk :). What I understood is , we have to count all the individual digits which divides the given number. Wiki page for divisibility.This problem is not allowed in Haskell so I am not sure if this solutions is correct as well fast enough to get accepted ( I requested problem setter to allow Haskell or move the same copy of problem in tutorial section with increased time limit ). All the divisibility rules are simple except seven [ Just iterated through the number and taking mod 7. We can also do mod ( fst . fromJust . BS.readInteger $ s ) 7 ) ]. Haskell code for this problem.

import Data.List import Data.Char import Data.Maybe ( fromJust ) import qualified Data.IntMap as M import qualified Data.ByteString.Lazy.Char8 as BS byteSum :: BS.ByteString -> Integer byteSum s = BS.foldr ( \x y -> y + ( fromIntegral . digitToInt $ x ) ) 0 s {-- testSeven :: BS.ByteString -> Integer testSeven s = sum. BS.zipWith (\x y -> fromIntegral $ digitToInt x * digitToInt y ) s . BS.pack. concatMap show . concat. repeat $ [ 1 , 3 , 2 , 6 , 4 , 5 ] --} numDiv :: Int -> BS.ByteString -> Bool numDiv a s | a == 0 = False | a == 1 = True | a == 2 = if even . digitToInt . BS.last $ s then True else False | a == 3 = if mod ( byteSum s ) 3 == 0 then True else False | a == 4 = if mod ( fst . fromJust . BS.readInt . BS.drop k $ s ) 4 == 0 then True else False | a == 5 = if mod ( digitToInt . BS.last $ s ) 5 == 0 then True else False | a == 6 = numDiv 2 s && numDiv 3 s | a == 7 = if BS.foldr ( \x y -> mod ( 10 * y + digitToInt x ) 7 ) 0 s == 0 then True else False | a == 8 = if mod ( fst . fromJust . BS.readInt . BS.drop m $ s ) 8 == 0 then True else False | a == 9 = if mod ( byteSum s ) 9 == 0 then True else False where len = BS.length s k = len - 2 m = len - 3 solve :: BS.ByteString -> BS.ByteString solve s = BS.pack.show $ ret where mp = BS.foldr ( \x y -> M.insertWith (+) ( digitToInt x ) 1 y ) M.empty s key = M.keys mp ret = foldr ( \x y -> if numDiv x s then y + ( fromJust . M.lookup x $ mp ) else y ) 0 key main = BS.interact $ BS.unlines . map solve . BS.lines

Advertisements

Cool problem. Yes, it does seem like ‘7’ is the tricky case. I am trying to think of a way to do this without resorting to integer division of the entire number by 7 (could be important if the algorithm needs to work with any size input). Using the idea that if (n mod 7 == 0), then ((n – 1) mod 7 == 0), perhaps a loop like this:

1) While (least significant digit /= 0), n = n -7

2) Right-shift i.e. (n = n / 10), because if ’10 * n’ is a multiple of 7, then so is n

You will eventually end up with just one digit; either 0 (if n is divisible by 7) or /= 0 if not

Comment by gcbenison | February 14, 2012 |