# Missing Numbers (FP)

# Missing Numbers (FP)

SurgicalSteel + 0 comments Dear Hackerrank team,

Please increase time limit for F# (Fsharp) programming language.

You give Haskell 5s, Clojure 8s, Scala 7s, Erlang 12s. And you give F# just for 4s???

IT IS NOT FUNNY!

shijinabraham + 1 comment " Can you find the missing numbers from A without messing up his order?" I didn't understand the meaning of this statement in the problem description

plilja + 1 comment I think it's a reference to the first sentence about comparing the lists without sorting.

shijinabraham + 0 comments thank you

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

Jonnymoo + 1 comment "Sometimes you need to compare lists of number, but sorting each one normally will take too much time. Instead you can use alternative methods to find the differences between each list."

Probably me missing the point... Isn't the quickest method to sort a and b and then do a scan difference between the two lists. You can sort in O(n log n) then scan diff in O(n) whereas if you diff without sorting first you are O(n squared).

Like I say, I may have totally missed the point (or got my times completely wrong). I don't understand the why we are told not to sort each one normally.

Incedently, I did sort a and b before implementing my diff, and it passed.

CKoenig + 0 comments because there is an algorithm that runs in O(n+m)

Odiumediae + 0 comments Pretty easy with Erlang, just some IO and: List2 -- List1

Sort 15 Discussions, By:

Please Login in order to post a comment