Both Solution O(logn) and O(n)


#1

O(n) Solution
int Solution::solve(vector &A) {
int XOR=0;
for(auto x:A)
XOR ^= x;
return XOR;
}

O(logn) Solution
int Solution::solve(vector &A) {
if(A.size() == 1 or A[0] != A[1])
return A[0];
if(A[A.size()-1] != A[A.size()-2])
return A[A.size()-1];
int s=0, e=A.size()-1;
while(s < e){
int mid = s + (e-s)/2;
if(mid > 0 and mid < A.size()-1 and A[mid] != A[mid-1] and A[mid] != A[mid+1])
return A[mid];
if(mid&1){
if(A[mid] == A[mid+1])
e = mid;
else
s = mid;
}
else{
if(A[mid] == A[mid+1])
s = mid;
else
e = mid;
}
}
}