I tried to solve the Unfriendly Number problem on InterviewStreet:

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 \le N \le 10^6\$

\$1 \le K \le 10^13\$

\$1 \le\$ unfriendly numbers \$\le 10^{18}\$

The 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?

  • \$\begingroup\$ 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. \$\endgroup\$
    – huon
    Aug 24, 2012 at 15:30
  • \$\begingroup\$ can we see your nubOrd? You compile it with -O2 right? \$\endgroup\$
    – Will Ness
    Aug 24, 2012 at 15:39
  • \$\begingroup\$ the nubOrd is the one here: stackoverflow.com/a/3100764/303863 \$\endgroup\$
    – Chao Xu
    Aug 24, 2012 at 16:10

1 Answer 1


Your divisors generation is lacking. As explained e.g. here, you should generate them from a number's prime factorization. It is much faster that way.

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.

update so I tried my own advice and it only made the code run slower at the interviewstreet servers. The only reason I'm not removing this, is that the advice itself (and link) about divisor generation is valid in general. But here, it did not help improve the run time of this algorithm. The OP states that same algorithm in Java got through...

  • \$\begingroup\$ InterviewStreet may not compile Haskell code with -O2. \$\endgroup\$
    – codygman
    Jul 17, 2014 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.