Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Approach: Lets have a look at the solution first and then I will explain what exactly this is doing. Here is the pseudo code -

ones = 0
twos = 0
notThrees = 0
FOREACH elem in array
twos = twos OR (ones AND elem)
ones = ones XOR elem
notThrees = NOT (twos AND ones)
ones = ones AND notThrees
twos = twos and notThrees
return ones;

Now let's understand what this is doing. This works in similar line with the question of  "finding the element which appears once in an array - containing other elements each appearing twice". Solution is to XOR all the elements and you get the answer. Basically, it makes use of the fact that x^x = 0 or I would say if "bit1" and "bit2" are same then bit1 ^ bit2 will become 0 so using XOR we actually cancel all the set bits appearing even times and remaining are set bits occurred odd times. Obviously these set bits give the number appears only once in an array.

Now, coming to our original question just XORing will not work as we will end up getting XOR of all unique elements. To make it work the solution uses 2 variables -

1. ones - At any point of time, this variable holds XOR of all the set bits which have appeared only once.
2. twos - At any point of time, this variable holds XOR of all the bits which have appeared only twice.

So here is the flow. I am using number instead of set bit just for make it more understandable (even though it is not true) -

1. A new number appears - It gets XOR'd to "ones"
2. A number appears twice - It is removed from "ones" and XOR'd to "twos"
3. A number appears for the third time - It gets removed from both "ones" and "twice"

Finally variable ones obviously will be our answer so if we can prove that above code is doing exactly these three steps we are done. The last three lines -

1. not_threes = NOT (ones & twos)
2. ones = ones AND not_threes
3. twos = twos AND not_threes

All it does is, common set bits between "ones" and "twos" are converted to zero because if a number comes ones and twice i.e. it appears three times and we don't want to include it in our answer. I simplify it just to make it more understandable.

Let's take an example array = [x, x, x, y] and run our code and see what it is doing -

For array[0] i.e. x -

1. twos = twos OR (ones AND x) - Since bit representation of "x" is not present in "ones", AND condition yields nothing. So "twos" does not get bit representation of "x" i.e. twos remain 0.
2. ones = ones XOR x - "ones" ends up adding bits of x
3. Last 3 lines will not do anything as there are no common set bits between ones and twos (x appears only once) so ones has x and twos is 0.

For array[1] i.e. x -

1. twos = twos OR (ones AND x) - twos will get bit representation of x and it should as x appears twice now.
2. ones = ones XOR x - "ones" ends up being 0 that is removing x's bit representation and it should as x is appeared twice now.
3. Last 3 lines will not do anything as there are no common set bits between ones and twos so twos will have x and ones will be 0.

For array[2] i.e. x -

1. twos = twos OR (ones AND x) - twos will get bit representation of x as ones(currently 0) & x will be 0 only.
2. ones = ones XOR x - ones will get get bit representation of x. (0 ^ x = x)
3. Here is problem as x is in twos and also in ones that's where last 3 lines of code do the magic as x's set bits are the common set bits in twos and ones so both of them will loose bit representation of x i.e. in our case ones and twos will become 0 and that's exactly we want. 

For array[2] i.e. y - Same as step 1 here ones will get the y and will be our answer. 

Hopefully it will make the solution understandable. Ultimately like XOR (in case of 2 element), we wanted an operation "op" which does the same thing, which XOR does on 2 elements, on 3 elements. Something like -

• x op x op x = 0
• 0 op x = x

which is exactly what we have achieved here. 

        public int SingleNumber2(int[] nums)

        {

            int ones = 0;

            int twos = 0;

            foreach(int num in nums)

            {

                twos |= ones & num;

                ones ^= num;

                int notThree = ~(ones & twos);

                ones &= notThree;

                twos &= notThree;

            }

            return ones;

        }