Number which occurs only once in the array

Question

Possible Duplicate:
Finding a single number in a list

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

Example

a[1..n] = [1,2,3,4,3,1,2] 

should return 4

Answer 1

Let the number which occurs only once in the array be x

x <- a[1]
for i <- 2 to n
   x <- x ^ a[i]
return x

Since a ^ a = 0 and a ^ 0 = a

Numbers which occur in pair cancel out and the result gets stored in x

Working code in C++

#include <iostream>

template<typename T, size_t N>
size_t size(T(&a)[N])
{
    return N;
}
int main()
{
   int a [] = {1,2,3,4,3,1,2};
   int x = a[0];
   for (size_t i = 1; i< size(a) ; ++i)
   {
      x = x ^ a[i];
   }
   std::cout << x;
} 

Answer 2

1. Create new int i = 0
2. XOR each item with i
3. After all iterations there will be expected number in i

Answer 3

If you have quantities which cannot be reasonably xored (Big Integers or numbers represented as Strings, for example), an alternate approach which is also O(n) time, (but O(n) space rather than O(1) space) would be to simply use a hash table. The algorithm looks like:

Create a hash table of the same size as the list
For every item in the list:
     If item is a key in hash table
         then remove item from hash table
         else add item to hash table with nominal value
At the end, there should be exactly one item in the hash table

I would do, C or C++ code, but neither of them have hash tables built in. (Don't ask me why C++ doesn't have a hash table in the STL, but does have a hash map based on a red-black tree, because I have no idea what they were thinking.) And, unfortunately, I don't have a C# compiler handy to test for syntax errors, so I'm giving you Java code. It's pretty similar, though.

import java.util.Hashtable;
import java.util.List;

class FindUnique {
    public static <T> T findUnique(List<T> list) {
        Hashtable<T,Character> ht = new Hashtable<T,Character>(list.size());
        for (T item : list) {
            if (ht.containsKey(item)) {
                ht.remove(item);
            } else {
                ht.put(item,'x');
            }
        }
        return ht.keys().nextElement();
    }
}

Answer 4

Well i only know of the Brute force algo and it is to traverse whole array and check

Code will be like (in C#):

k=0;
for(int i=0 ; i < array.Length ; i++)
{
    k ^= array[i];
}
return k;

Answer 5

zerkms' answer in C++

int a[] = { 1,2,3,4,3,1,2 };

int i = std::accumulate(a, a + 7, 0, std::bit_xor<int>());

Answer 6

You could sort the array and then find the first element that doesn't have a pair. That would require several loops for sorting and a loop for finding the single element.

But a simplier method would be setting the double keys to zero or a value that is not possible in the current format. Depends on the programming language, as well, as you cannot change key types in c++ unlike c#.