We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Functional Programming
  3. Ad Hoc
  4. Missing Numbers (FP)
  5. Discussions

Missing Numbers (FP)

  • penkovsky
     + 0 comments

    Spoiler alert.

    First, I use strict IntMap's to efficiently count the number of occurrences of each element in both lists.

    import qualified Data.IntMap.Strict as M

buildMap :: M.IntMap Int -> [Int] -> M.IntMap Int
buildMap m [] = m
buildMap m (x:xs) = let count = M.lookup x m
                        m' = update m x count
                    in buildMap m' xs

update :: M.IntMap Int -> Int -> Maybe Int -> M.IntMap Int
update m x Nothing = M.insert x 1 m
update m x (Just cnt) = M.insert x (cnt + 1) m

    Then, I define a function to compare both IntMap's by (unique) keys.

    cmp num cnt1 cnt2 = if cnt1 > cnt2 then Just num else Nothing

    It means, if a number num occurs more times in the first list than in the second one, then we are looking for it. Finally, the program is simple:

    main = do
  -- Build the first IntMap
  _ <- getLine
  a <- (buildMap M.empty . map read . words) <$> getLine

  -- Build the second IntMap  
  _ <- getLine
  b <- (buildMap M.empty . map read . words) <$> getLine
  
  -- Find the differences
  let diffs = M.differenceWithKey cmp b a
  
  -- Print
  putStrLn . unwords . map (show . fst) . M.toList $ diffs