Partition the number according to bits. Elegant solution


#1

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){
if(val&mask){
count++;
}
}
ans|=(count%3)<<i;

}
return ans;

}


#2

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.


#3

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)