Algorithm to find a number which occurs only once in an array, given all the other numbers occur twice [duplicate]

Question

What I can think of is:

Algo:

1. Have a hash table which will store the number and its associated count
2. Parse the array and increment the count for number.
3. Now parse the hash table to get the number whose count is 1.

Can you guys think of solution better than this. With O(n) runtime and using no extra space

Answer 1

Assuming you can XOR the numbers, that is the key here, I believe, because of the following properties:

• XOR is commutative and associative (so the order in which it's done is irrelevant).
• a number XORed with itself will always be zero.
• zero XORed with a number will be that number.

So, if you simply XOR all the values together, all of the ones that occur twice will cancel each other out (giving 0) and the one remaining number (n) will XOR with that result (0) to give n.

r = 0
for i = 1 to n.size:
    r = r xor n[i]
print "number is " + r

No hash table needed, this has O(n) performance and O(1) extra space (just one tiny little integer).

Answer 2

An answer in Ruby, assuming one singleton, and all others exactly two appearances:

def singleton(array)
  number = 0
  array.each{|n| number = number ^ n}
  number
end

irb(main):017:0> singleton([1, 2, 2, 3, 1])
=> 3

^ is the bitwise XOR operator, by the way. XOR everything! HAHAHAH!

Rampion has reminded me of the inject method, so you can do this in one line:

def singleton(array) array.inject(0) { |accum,number| accum ^ number }; end

Answer 3

"Parse the array and increment the count for number."

You could change this to "Parse the array and if the number already exists in the hash table, remove the number from the hash table". Then step 3 is just "get the only number that remains in the hash table"