I tried to solve the Unfriendly Number problem on InterviewStreet.

Statement:

There is one friendly number, K, and N unfriendly numbers. We want to find how many numbers are there which exactly divide the friendly number, but does not divide any of the unfriendly numbers.

1 <= N <= 10^6

1 <= K <= 10^13

1 <= unfriendly numbers <= 10^18

Algorithm is quite simple:

1. Find the set S. The set of gcd's of each unfriendly number with the friendly number.
2. Find the set of divisors of the friendly number.
3. Check if a divisor of the friendly number is a divisor of any element in S.

My code, where `u` is the list of unfriendly numbers, `k` is the friendly number. `nubOrd` is the `O(n log n)` time version of `nub`.

``````test u k = length \$ filter (not) \$ map try divisors
where try t = or \$ map (t `divides` ) (nubOrd \$ map (gcd k) u)
divisors = concat [ [i,div k i] | i<-[1..floor \$ sqrt \$ fromIntegral k],
i `divides` k]
d `divides` n = n `mod` d == 0
``````

This code exceeds the time limit. The Java version of this algorithm solves the problem fine. Are there any ways to improve this code or is Haskell too slow for solving this problem?

-
It might be more efficient to replace the `length . filter not . map try` chain with a fold like `foldl (\count t -> if try t then count + 1 else count) 0` (probably with more strictness). But it's unlikely to make that much difference, since GHC is pretty smart. –  dbaupp Aug 24 '12 at 15:30
can we see your `nubOrd`? You compile it with -O2 right? –  Will Ness Aug 24 '12 at 15:39
the nubOrd is the one here: stackoverflow.com/a/3100764/303863 –  Chao Xu Aug 24 '12 at 16:10

## migrated from stackoverflow.comAug 25 '12 at 17:59

This question came from our site for professional and enthusiast programmers.

You may try using `rem` instead of `mod`.
Also try making `(nubOrd \$ map (gcd k) u)` a separate expression and name it to ensure sharing, giving your function a concrete type signature too.