Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

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

This is an extremely tricky problem.

First, we consider each bit of the 32bits integer.

Each bit can be either 1 or 0. Let’s consider bit[0] as an example. other bits(bit[31~1]) are similar to bit[0].

Since every integer appears three times except for one, 1 and 0 also appears in multiples times of three or with one over. If the count of 1 can be divided by 3, the bit 0 of the single appearance number is 0.

If the count of 1 can be divided by 3 with one over, the bit 0 of the single appearance number is 1.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int digits[32]; // digits[0] lowest digit, digits[31] highest digit
        int re = 0;
        memset(digits, 0, sizeof(digits));
        for(auto it = nums.begin(); it != nums.end(); it++){
            for(size_t i = 0; i < 32; i++){
                digits[i] = (digits[i] + (((*it) >> i) & 0x00000001)) % 3;
            }
        }
        for(int i = 31; i >= 0; i--){//i should be declared as int, not size_t.
            re = (re << 1) + digits[i];
        }
        return re;
    }
};