Partition the number according to bits. Elegant solution


int Solution::singleNumber(const vector &A) {
int ans=0;
for(int i=31;i>=0;i–){
int mask=1<<i;
int count=0;
for(auto val:A){

return ans;



This actually is O(nlogn) as every bit of a number can be accesed in logn time. And for a 32 loop, this would even exceed nlogn.


I wonder what you are considering ‘n’ to be
If we consider n to be the length of array then time complexity will be O(32nlog(32)) since every bit of a number will be accessed in log(32) time and not log(n) as there are 32 bits in an integer.
Further simplifying complexity, it will come out to be O(n)