Algorithm to find a number which occurs only once in an array, given all the other numbers occur twice
algorithm, language-agnostic
Solution
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
Problem
What I can think of is: Algo: - Have a hash table which will store the number and its associated count - Parse the array and increment the count for number. - 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