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

Hello.

Trying to find the only element that does not appear twice I wrote the following algorithm:

``````list = [1, 2, 3, 1, 3, 10, 200, 10, 200] # Expected result => 2

def single_one(list) do
list
|> Enum.reduce(%MapSet{}, fn x, acc ->
if MapSet.member?(acc, x) do
MapSet.delete(acc, x)
else
MapSet.put(acc, x)
end
end)
|> MapSet.to_list()
|> hd()
end
``````

I have the following questions:

1. I would like to know if in Elixir it is good practice to use if else as I did in the previous algorithm.
I could not find a way to access the first and only element of the MapSet.
I proceeded to convert the MapSet into a list and then its head.
2. Is there a better way to get the first element of a MapSet?

Any suggestions to improve the algorithm is welcome.

Thanks.

1 Like

In cases like this, where you check for a boolean result, `if/else` is usually used instead of `case`, so itās good as is .

I donāt think there is, because there is no āfirstā element in a MapSet. In this case, you know that there is only a single one, but in the more general case, elements inside a MapSet are not ordered. So if you have more than a single element in a set, there is no idea which element youād obtain when extracting a single one from it.

1 Like

Hi @Qqwy. Thanks for your response.

I donāt think there is, because there is no āfirstā element in a MapSet.

Could you be so kind to explain me how I can refer to the first element of a MapSet? Or what do you mean there is not a first element in a MapSet?
The official definition of MapSet says the following:

A set can contain any kind of elements, and elements in a set donāt have to be of the same type.

Thanks so much!

I would suggest something similar to a counting sort. That would only take O(2n) if you know the range O(3n) if you donāt.

1 Like

Elements in Maps and MapSets are not ordered. So whichever element appears āfirstā is ārandomā, i.e. is implementation dependent.

2 Likes
``````use Bitwise
[1, 2, 3, 1, 3, 10, 200, 10, 200] |> Enum.reduce(0, &Bitwise.bxor/2)
#ā 2
``````

7 Likes

Classic methods are always the best one.

3 Likes

Hi @peerreynders.
Thank you very much for clarifying my question.

Hello @mudasobwa

This is amazing:

``````use Bitwise
[1, 2, 3, 1, 3, 10, 200, 10, 200] |> Enum.reduce(0, &Bitwise.bxor/2)
#ā 2
``````

Thanks so much for sharing!

1 Like

This will fail badly when someone puts a number thriceā¦

1 Like

Find the element that appears once in an array where every other element appears twice

Feels like a solution that was looking for a problem statement

1 Like

Also, it will fail even worse on any non-integer

1 Like

The input was defined, yes. But still I consider it important to tell about the problems of this approach.

I consider crashing with an error not worse than a result that is confusingā¦

``````iex(1)> require Bitwise
Bitwise
iex(2)> [1, 2, 3, 1, 3, 10, 200, 10, 200, 200] |> Enum.reduce(0, &Bitwise.bxor/2)
202
``````

202 was not even in the listā¦

2 Likes

FWIW, Iād provide a bare implementation that is similar to `MapSet` (actually it replicates `MapSet` implementation, which is a bare map underneath):

``````[1, 2, 3, 1, 3, 10, 200, 10, 200] |> Enum.reduce(%{}, fn e, acc ->
if is_nil(Map.get(acc, e)), do: Map.put(acc, e, e), else: Map.delete(acc, e)
end) |> Map.keys() |> hd()
#ā 2
``````
3 Likes

@mudasobwa All your ideas are welcome.
I really liked this implementation:

``````if is_nil(Map.get(acc, e)), do: Map.put(acc, e, e), else: Map.delete(acc, e)
``````

Thanks so much!

Nobody would write it like this - but āreplace conditional with pattern matchā.

``````[1, 2, 3, 1, 3, 10, 200, 10, 200] |> List.foldl(%{}, fn e, acc ->
{_, acc} = get_and_update_in(acc, [e],
fn
:nil ->
{e, e}
_ ->
:pop
end)
acc
end) |> Map.keys() |> hd()
``````
1 Like

Yes! Thatās what Iām looking for, new ideas to solve problems.
Now I need to study your code

Although a bit of an overkill you can also use an `ets` table to use as a counter table.

``````list = [1, 2, 3, 1, 3, 10, 200, 10, 200, 10]

counter_table = :ets.new(:counter_table, [])
Enum.each(list, fn(x) -> :ets.update_counter(counter_table, x, 1, {x, 0}) end)

selector = fn(table, n_occurr) ->
case :ets.select(table, [{{:"\$1", n_occurr}, [], [:"\$1"]}]) do
[x] -> x
multiple_or_none -> {:error, multiple_or_none}
end
end

selector.(counter_table, 1)
# 2

selector.(counter_table, 2)
# {:error, [200, 1, 3]}

selector.(counter_table, 3)
# 10

selector.(counter_table, 4)
# {:error, []}

:ets.delete(counter_table)
# true
``````
1 Like

Super impresive. Really love it! Thanks so much for sharing!

You could also create a histogram (which takes O(n) time), and then drop all elements from it that have a count of ā2ā. You then end up with:

1. either exactly one element, and you can output it
2. Something that does not match the input you expect, and youāre now able to return or raise a proper error.

I think that might be a more robust solution, if you cannot be entirely sure that the input precondition is met by the user at all times. It will also work for non-integers. (Although the binary XNOR is a marvellous idea )

4 Likes