### Question

Given an array of integers, every element appears *three* times except for one. Find that single one.

**Note:**

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

### Stats

$Adjusted Difficulty | 5 |

Time to use | -------- |

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

**This is an extremely difficult question**. There are 2 solutions (both are bit manipulation).

### Solution

**First solution comes from this forum**.

A straightforward implementation is to use an array of size 32 to keep track of the total count of ith bit.

A more detailed explanation:

For eg : A = [ 2, 3, 3, 3]We count the number of 1s for each bit position. Then findmod 3of each of them. The bit positions havingmod 3equal to one are the bits that are set due to the number occurring once.Writing the Binary Representation of the numbers.0 0 1 00 0 1 10 0 1 10 0 1 1----------------We count the number of 1s for each bit -> 0 0 4 3Taking modulo 3 we get 0 0 1 0and that's our answer. -> 2

**Second solution is different, and very hard to read/write**. I will not cover this solution. An analysis is found here:

The basic idea is use two integer,

ones and twos.Onesis used to record the bits only exist once in current iterated number.Twosis used to record the bits only exist twice in all number. If a bit exists up to three times, we should clear it in both ones and twos.

### Code

**my code**

```
public int singleNumber(int[] A) {
int result = 0;
for (int i = 0; i < 32; i++) {
int count = 0;
for (Integer in: A) {
count += (in & (1 << i)) == 0 ? 0 : 1;
}
if (count % 3 != 0) {
result = result | (1 << i);
}
}
return result;
}
```

**a different solution**

```
public int singleNumber(int[] A) {
int ones = 0, twos = 0;
for (int i = 0; i < A.length; i++) {
twos = twos | (ones & A[i]);
ones = ones ^ A[i];
int common_mask = ~(ones & twos);
ones &= common_mask;
twos &= common_mask;
}
return ones;
}
```