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;
    }
};