LeetCode: 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?


Idea: if we look all the last bit of the numbers (assuming all are 32-bit) in the array, there must be 3k+1 or 3k `1's in total depending whether the single number's last bit is one or zero. This observation holds for all the rest 31 bits as well. Hence, if we sum all the numbers only at certain bit and mod by 3, we can get the corresponding bit the single number. Do this for all 32-bit, we can get all bits of that number. This generalizes the solution of LeetCode: Single Number I, where xor all the numbers is essentially trying to add all bits and then mod by 2...




Solution in C++:

class Solution {
public:
    int singleNumber(int A[], int n) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int single_number = 0;
        for (int i = 0; i < 32; ++i) {// assume dealing with int32.
            int bit = 0;
            for (int j = 0; j < n; ++j) {
                bit = (bit + ((A[j] >> i) & 1)) % 3;
            }
            single_number += (bit << i);
        }
        return single_number;
    }
};