Andres
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:
- 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. - Is there a better way to get the first element of a MapSet?
Any suggestions to improve the algorithm is welcome.
Thanks.
Marked As Solved
mudasobwa
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
Also Liked
mudasobwa
use Bitwise
[1, 2, 3, 1, 3, 10, 200, 10, 200] |> Enum.reduce(0, &Bitwise.bxor/2)
#⇒ 2
Qqwy
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:
- either exactly one element, and you can output it
- 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 
)
hauleth
Classic methods are always the best one.
hauleth
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).
peerreynders
Elements in Maps and MapSets are not ordered. So whichever element appears “first” is “random”, i.e. is implementation dependent.
Popular in Questions
Other popular topics
Latest on Elixir Forum
Sponsor Spotlight
Producing high quality Elixir screencasts since 2017.
Categories:
Sub Categories:
Forums
Our Sponsors
Build Elixir applications with speed and confidence.
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Practical resources that improve the lives of professional developers.
Producing high quality Elixir screencasts since 2017.
Enabling companies to succeed by building software people love.
Courses that'll move you from confusion to "Aha, now I get it!"