# 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):
mask = 1 << i
total = 0
for num in nums:
if num & mask:
total += 1
if total % 3: # generalization: if total % Y == X
result |= mask
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;
}
};