# Question

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

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

Example 1:

```
Input: [2,2,3,2]
Output: 3
```

Example 2:

```
Input: [0,1,0,1,0,1,99]
Output: 99
```

# Solution

To determine how many occurrences of an integer there are up to a maximum of three. We need to build a 3 state counter.

How do we do that? Boolean logic. Consider a single bit input and how that would drive the internal state of a bit counter in the state table below. An input value ‘0’ does not change the internal state. Input of ‘1’ drives the counter from state 0, 1, 2 and resets back to zero.

```
/* 3-state counter */
'A' 'twos' 'ones' 'twos' 'ones'
0 0 0 | 0 0
0 0 1 | 0 1
0 1 0 | 1 0
1 0 0 | 0 1
1 0 1 | 1 0
1 1 0 | 0 0
```

How to derive the state transfer from the above state table? Karnaugh map.

`ones = A XOR ones if twos == 0 else 0`

, and `twos = twos XOR A if new_ones == 0 else 0`

, in which `new_ones`

is the output from statement 1.

```
for (int i = 0; i < A.size(); i++) {
ones = (ones ^ a[i]) & ~twos;
twos = (twos ^ a[i]) & ~ones;
}
```

We can extend the same approach to a 4-state counter, which works on the same problem if we want to find a single occurrence among multiple occurrences of 4 values. The state table extends by one count before resetting, and we have a new set of boolean logic. Again, other boolean constructions are possible for the same state table.

```
/* 4-state counter */
'A' 'twos' 'ones' 'twos' 'ones'
0 0 0 | 0 0
0 0 1 | 0 1
0 1 0 | 1 0
0 1 1 | 1 1
1 0 0 | 0 1
1 0 1 | 1 0
1 1 0 | 1 1
1 1 1 | 0 0
for (int i = 0; i < A.size(); i++) {
ones = (ones ^ A[i]);
twos = (twos | A[i]) & (~A[i] | (ones ^ twos));
}
```

For 5 states we would need to add a third bit as a ‘threes’ variable and additional logic design.

```
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ones, twos = 0, 0
for n in nums:
ones = (ones ^ n) & ~twos
twos = (twos ^ n) & ~ones
return ones
```