Given an array of numbers, only one number appears once, others twice. Find the number.

If there's only 1 number appearing once, it's actually easier. just use xor. The duplicate values cancel out since their xor is 0

int unique_number(const vector<int>& a) {
	int ans(0);
	for (size_t i=0; i < a.size(); i++) 
		ans ^= a[i];
	return ans;
}

 

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;
} 

 

What if two numbers appear once, what if 500 numbers appear once. How to find these numbers.?

I think hashes are definitely needed. Thus you find all numbers appeared once in O(n) time. Some quick example below (in Ruby):

def find_single(ar)
    num_hash = Hash.new(2)
    ar.each do |n| 
        num_hash[n] -= 1
        num_hash.delete(n) if num_hash[n] <= 0
    end

    return num_hash.keys
end

 

http://www.sysexpand.com/?path=exercises/number-appearing-once-in-array

END