# Linear time with no extra memory

• this is my solution with time O(a*n) where a is the length of the integer. I solve the problem by using a counting sort (O(n)) method at each digit of the numbers (start from the lowest digit and thus the order is stable) and gradually locate the position of the single number cauz the singular number makes the count of 0s (or 1s) an odd number at that digit.

``````class Solution {
public:
int singleNumber(int A[], int n){
//the digits of integers
int length=8*sizeof(int);
int count0,count1;
//lookup range
int posp=0,posq=n-1;
//for each digit
for(int i=0;i<length;i++){
if(posp==posq) return A[posp];
//counting 0s and 1s
count0=0;count1=0;
for(int j=posp;j<=posq;j++){
if((A[j]&(1<<i))==0)count0++;
else count1++;
}
//swaping integers with 0s to the front(order stable)
int pos0=posp,curpos=posp;
while(curpos<=posq){
if((A[curpos]&(1<<i))==0){
int temp=A[pos0];
A[pos0]=A[curpos];
A[curpos]=temp;
pos0++;
}
curpos++;
}
//relocate
if(!(count0%2))posp+=count0;
else posq-=count1;
}
return A[posp];
}
};``````

• why not:

``````    int singleNumber(int A[], int n) {
int x = 0;
for(int i=0; i<n; i++)
x ^= A[i];
return x;
}
``````

• Thanks, that's a short and smart answer. I thought about finding the position of the number only

• Hi, haomaoer.

Base your idea, I write this code.

``````class Solution {
public:
int singleNumber(int A[], int n) {
int ret = 0;
int count0 = 0;
int count1 = 0;
for (int i=0; i < sizeof(int)*8; ++i)
{
count0=0;
count1=0;
for (int j=0; j < n; ++j)
{
if (A[j]&(1<<i))
{
++count1;
}
else
{
++count0;
}
}
if (count1%2)
{
ret |= 1<<i;
}
else
{
// this bit of ret is 0
}
}

return ret;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.