R@M3\$H.NBlog

# [ARRAY] Find Num which Appears Once

### 30 September, 2013 - 2 min read

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&lt;int&gt;&amp; a) {
int ans(0);
for (size_t i=0; i &lt; a.size(); i++)
ans ^= a[i];
return ans;
}``````

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

``````x &lt;- a[1]
for i &lt;- 2 to n
x &lt;- 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 &lt;iostream&gt;

template&lt;typename T, size_t N&gt;
size_t size(T(&amp;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&lt; size(a) ; ++i)
{
x = x ^ a[i];
}
std::cout &lt;&lt; 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] &lt;= 0
end

return num_hash.keys
end``````

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

END