Given a non-empty list of integers, every element appears twice except for one. Find that single one

Questions / Help
,
21

I saw this and immediately thought of the frequencies function in Clojure’s standard library.

Returns a map from distinct items in coll to the number of times they appear.

I’m not sure if Elixir’s standard library has such a function, but here’s a simple implementation:

frequencies = fn(enumerable) ->
  for {k, v} <- Enum.group_by(enumerable, &(&1)), into: %{}, do: {k, length(v)}
end

Example usage:

iex(4)> frequencies.(~w(a b c a c d d e e e f))
%{"a" => 2, "b" => 1, "c" => 2, "d" => 2, "e" => 3, "f" => 1}

And here’s how we can use frequencies to find the singleton(s):

iex(6)> xs = ~w(a b c a c d d e e e f)
["a", "b", "c", "a", "c", "d", "d", "e", "e", "e", "f"]
iex(7)> for {x, freq} <- frequencies.(xs), freq == 1, do: x
["b", "f"]
1 Like
22

It can be pretty slow as you are iterating through all elements twice. Instead it is better to use:

inc = & &1 + 1
Enum.reduce(enumerable, %{}, &Map.update(&2, &1, 1, inc))

But in this case if this is homework and you know that the constraints will always hold then XOR solution by the @mudasobwa. If you do not know whether it will integer-only or you do not know if there will be only one value that occurs odd number of times, then second solution with map (however I would use Map.has_key?/2 or Map.fetch/2 instead of Map.get/2 as it is less quirky).

3 Likes
23

Agreed, that simple implementation of frequencies isn’t optimal.

Here’s how Clojure actually does it:

(defn frequencies
  "Returns a map from distinct items in coll to the number of times
  they appear."
  {:added "1.2"
   :static true}
  [coll]
  (persistent!
   (reduce (fn [counts x]
             (assoc! counts x (inc (get counts x 0))))
           (transient {}) coll)))

So it looks like your approach and Clojure’s are pretty much the same, although in Clojure’s case it is manipulating a mutable map (the (transient {}) part) and then rendering it immutable upon return (the (persistent! ...) part).

For those who are curious, here are more details about Clojure’s transient data structures.

I’m not sure if Elixir has something equivalent, or whether that’s even desirable in Elixir land.

I like your inc function, by the way. :slight_smile:

Clojure’s standard library offers inc and dec and thus they’re within easy reach.

It’s nice to see they’re so easily implemented in Elixir.

1 Like
24

Hmm, I just learned about the :reduce option in for comprehensions:

https://hexdocs.pm/elixir/Kernel.SpecialForms.html#for/1-the-reduce-option

Looks like my old, slow implementation of frequencies can change from this…

frequencies = fn(enumerable) ->
  for {k, v} <- Enum.group_by(enumerable, &(&1)), into: %{}, do: {k, length(v)}
end

…to this variation on @hauleth’s example:

inc = & &1 + 1
frequencies = fn(enumerable) ->
  for x <- enumerable, reduce: %{} do
    acc -> Map.update(acc, x, 1, inc)
  end
end

:icon_cool:

1 Like
25

Awesome! Thanks so much for sharing! :smiley:

2 Likes
26

And thank you for asking a related question, otherwise using :reduce wouldn’t have come to mind. :rocket:

1 Like