Codewars - Odd Integer

"Find the integer that appears an odd number of times in this list," says Codewars. "Sure," I say, "this ought to be fun."

Again, playing with Haskell and how I fare with it compared to Python.

Is it really a spoiler?


def find_it(seq):
  """Given a sequence of integers, return the one that appears an odd number of
  counts = {}

  for x in seq:
    counts[x] = counts.get(x, 0) + 1

  for c in counts:
    if counts[c] % 2 == 1:
      return c

This was a very simple problem; took a few minutes to copy the test locally and then write it all up.


findOdd :: [Int] -> Int
findOdd xs = oddInt $ Map.toList $ counts xs Map.empty where

  counts [] rsf = rsf
  counts (x:xs) rsf = counts xs
                    $ Map.insert x ((Map.findWithDefault 0 x rsf) + 1) rsf

  oddInt::[(Int,Int)] -> Int
  oddInt ((x,y):xs)
    | y `mod` 2 == 1 = x
    | otherwise = oddInt xs

Trying to re-implement the solution in Haskell gave me a chance to learn a little about the Data.Map module. As with other challenges, it took more effort and time to implement, though in this case it felt more like a problem of not knowing the module than wrestling the paradigm as a whole.


In this case I prefer what I did in Python; I managed to make the Map in Haskell work, but it seems clunky and hard to follow. It's a good bet that a major part of the issue is that I really took an imperative approach and attempted to simply translate it rather than having a strong functional one. Price of trying something new.

Nice solutions to study


Turns out that Python lists have a built in count function, so there is a much more simply expressed solution. My O notation skills are somewhat naive, but if python counts the way I think it does, the solution actually risks O(n)^2 - is that right?

A more efficient approach manages to dodge the dict entirely.


Apparently, understanding what happens with the bits is a super power.

... and yes, there are functional approaches that only need one line of composition and filtering.