Solving with o(n) time & aux. o(1)


#1

We can sum the bits in same positions for all the numbers and take modulo with 3. The bits for which sum is not multiple of 3, are the bits of number with single occurrence. And max bits for integer can be 32.
For ex. -> {6, 3, 3, 3}. The 110, 011, 011, 011
Sum of first bits%3 = (0 + 1 + 1 + 1)%3 = 0;
Sum of second bits%3 = (1 + 1 + 1 + 1)%0 = 1;
Sum of third bits%3 = (1 + 1 + 1 + 1)%3 = 1;
Hence number which appears once is 110 is 6. Here is your answer.

CODE :slight_smile:
public int singleNumber(final List A) {
int size = 32;
int n = A.size();
int sum = 0;
int answer = 0;
int num = 0;
for(int i=0;i<size;i++){
sum =0;
for(int j=0;j<n;j++){
num = A.get(j) >> i;
int x = num & 1;
sum+=x;
}
sum = sum%3;
answer += (int)sum*Math.pow(2,i);
}
return answer;
}