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

Questions / Help
,
1

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
2

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 :slight_smile: .

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
3

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!

4

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
5

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

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

:man_shrugging:

7 Likes
7

Classic methods are always the best one.

3 Likes
8

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

9

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
10

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

1 Like
11

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 :slight_smile:

1 Like
12

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

1 Like
13

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
14

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
15

@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!

16

Nobody would write it like this :slight_smile: - 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
17

Yes! Thatā€™s what Iā€™m looking for, new ideas to solve problems.
Now I need to study your code :smile:

18

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
19

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

20

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 :heart_eyes:)

4 Likes