Given an array of numbers, except for one number all the others, occur twice. Give an algorithm to find that number which occurs only once in the array.

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

"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"

Answer 2

Algo 2:

1. Sort the array.
2. Now parse the array and if 2 consecutive numbers are not same we got our number.
3. This will not use extra space

Answer 3

This doesn't fit the bill for "no extra space" but it will cut the space unless the numbers are sorted in a certain way.

In Python:

arr = get_weird_array()
hash = {}

for number in arr:
   if not number in hash:
     hash[number] = 1
   else:
     del hash[number]

for key in hash:
    print key

Answer 4

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 5

I'm stealing Michael Sofaer's answer and reimplementing it in Python and C:

Python:

def singleton(array):
    return reduce(lambda x,y:x^y, array)

C:

int32_t singleton(int32_t *array, size_t length)
{
    int32_t result = 0;
    size_t i;
    for(i = 0; i < length; i++)
        result ^= array[i];
    return result;
}

Of course, the C version is limited to 32-bit integers (which can trivially be changed to 64-bit integers if you so desire). The Python version has no such limitation.

Answer 6

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, O(n) performance, and O(1) extra space (just one tiny little integer).

Answer 7

Here's a solution in Python that beats the Ruby one for size (and readability too, IMO):

singleton = lambda x: reduce(operator.xor, x)

Answer 8

Python 3.1 Solution:

>>> from collections import Counter
>>> x = [1,2,3,4,5,4,2,1,5]
>>> [value for value,count in Counter(x).items() if count == 1 ][0]
3
>>>

• Paddy.