# 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