Question

link

Stats

$

Adjusted Difficulty	5
Time to use	--------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is an extremely difficult question. There are 2 solutions (both are bit manipulation).

Solution

First solution comes from this forum.

A straightforward implementation is to use an array of size 32 to keep track of the total count of ith bit.

A more detailed explanation:

For eg : A = [ 2, 3, 3, 3]

We count the number of 1s for each bit position. Then find mod 3 of each of them. The bit positions having mod 3  equal to one are the bits that are set due to the number occurring once.

Writing the Binary Representation of the numbers.

                                                                  0 0 1 0

                                                                  0 0 1 1

                                                                  0 0 1 1

                                                                  0 0 1 1

                                                            ----------------

We count the number of 1s for each bit ->  0 0 4 3

Taking modulo 3 we get                             0 0 1 0

and that's our answer. -> 2

Second solution is different, and very hard to read/write. I will not cover this solution. An analysis is found here:

The basic idea is use two integer, ones and twos. Ones is used to record the bits only exist once in current iterated number. Twos is used to record the bits only exist twice in all number. If a bit exists up to three times, we should clear it in both ones and twos.

Code

my code

public int singleNumber(int[] A) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        int count = 0;
        for (Integer in: A) {
            count += (in & (1 << i)) == 0 ? 0 : 1;
        }
        if (count % 3 != 0) {
            result = result | (1 << i);
        }
    }
    return result;
}

a different solution

public int singleNumber(int[] A) {
    int ones = 0, twos = 0;
    for (int i = 0; i < A.length; i++) {
        twos = twos | (ones & A[i]);
        ones = ones ^ A[i];

        int common_mask = ~(ones & twos);
        ones &= common_mask;
        twos &= common_mask;
    }
    return ones;
}