## # 137. Single Number II

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

Approach 1: Sorting.

Approach 2: Bit manipulation.

Approach 3: go through each bit (constant time) for each number, and count occurrences of 1s (or use if else statements to reflect the truth table).

### # Code (Python)

Approach 2:

``````    def singleNumber(self, nums):
# idea: have 3 states, so use a combination of 2 numbers (a and b) to represent this.
# https://cloud.tencent.com/developer/article/1131945
for num in nums:
b = (b ^ num) & (~a)
a = (a ^ num) & (~b)
return b
``````

Approach 3:

``````    def singleNumber1(self, nums: List[int]) -> int:
# assuming 32 bit integers
# idea: for each bit position, go through all nums and count the 1s, mod that by 3
# generalizable to X times all elements except Y times a single element
# time: 32N
result = 0
for i in range(32):
total = 0
for num in nums:
total += 1
if total % 3: # generalization: if total % Y == X
return self._convert(result)

# python specific because there's no highest bit (sign bit) in python
def _convert(self, result):
return result if result < (1 << 31) else result - (1 << 32)
``````

### # Code (C++)

Approach 1:

``````// Sorting.
class Solution {
public:
int singleNumber(vector<int>& nums) {
std::sort(nums.begin(), nums.end());
int i;
for (i = 0; i < nums.size(); i+=3)
{
if (i == nums.size() - 1 || nums[i] != nums[i+1])
break;
}
return nums[i];
}
};
``````

Approach 2:

``````// For the 1-bit interger case, if we see one number
// the counter should be 1 (01), if we see two numbers
// the counter should be 2 (10), and if we see 3 numbers
// the counter should loop back to 0. In order to have
// these 3 states we need 2 bits, hence a and b. For
// each input from the array, if we hit a 0, the counter
// should remain unchanged. For each input from the array,
// if we hit a 1, the counter should increase by one.
// Truth table:
// a b num -> a b
// 0 0 0   -> 0 0
// 0 1 0   -> 0 1
// 1 0 0   -> 1 0
// 0 0 1   -> 0 1
// 0 1 1   -> 1 0
// 1 0 1   -> 0 0
class Solution {
public:
int singleNumber(vector<int>& nums) {
int a = 0;
int b = 0;
for (int i = 0; i < nums.size(); ++i)
{
b = (b ^ nums[i]) & ~a;
a = (a ^ nums[i]) & ~b;
}
return b;
}
};
``````