Single Number II from leetcode

Question

The question about Single Number II from leetcode is:

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?

Actually, I already found the solution from website, the solution is:

public int singleNumber(int[] A) {
    int one = 0, two = 0;
    for (int i = 0; i < A.length; i++) {
        int one_ = (one ^ A[i]) & ~two;
        int two_ = A[i] & one | ~A[i] & two;
        one = one_;
        two = two_;
    }
    return one;
}

However, I do not know why this code can work and actually I do not know the way of thinking of this problem when I first saw it? Any help. thx!

Answer 1

The idea is to reinterpret the numbers as vectors over GF(3). Each bit of the original number becomes a component of the vector. The important part is that for each vector v in a GF(3) vector space the summation v+v+v yields 0. Thus the sum over all vectors will leave the unique vector and cancel all others. Then the result is interpreted again as a number which is the desired single number.

Each component of a GF(3) vector may have the values 0, 1, 2 with addition being performed mod 3. The "one" captures the low bits and the "two" captures the high bits of the result. So although the algorithm looks complicated all that it does is "digitwise addition modulo 3 without carry".