# 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

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

lightyear1 + 0 comments Waay easier when I carefully read the description. It says not to sort input array, but it does not say that the output array should follow the order of inputs. Actually output must be sorted:

import Control.Monad (replicateM) import Data.List (sort, (\\)) import qualified Data.Set as Set solve :: [Int] -> [Int] -> [Int] solve a b = b \\ a main :: IO () main = do [a, b] <- replicateM 2 (do factorCount <- readLn :: IO Int map read . words <$> getLine :: IO [Int] ) putStrLn $ unwords $ map show $ Set.toList $ Set.fromList $ solve a b

weozUA + 0 comments import scala.io.StdIn object Solution extends App { val (_, l1, _, l2) = ( StdIn.readInt(), StdIn.readLine().split(" "), StdIn.readInt(), StdIn.readLine().split(" "), ) l2.diff(l1).distinct.sorted.foreach(i => print(s"$i ")) }

mariuszdelta + 0 comments cheers

(a.diff(b) ++ b.diff(a)).distinct.sorted.foreach(i => print(s"${i} "))

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)

mighty12 + 1 comment testcase 2 failing. checked test case. Test Case:(array1 1000 elements, array2 1009 element, but result 8 elements) Am i missing something or test case in wrong, as resulting difference should be 9 elements not eight

Sort 12 Discussions, By:

Please Login in order to post a comment