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?

Solution : 

Came across a beautiful solution in the official LeetCode's Discuss section.

Unfortunately no explanation was offered, hence will try to explain it here.

As in the case of the Single Number question, we need to manipulate the bits of the numbers in the array.

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

Here's the code : 

The code basically has 2 variables  one & two. 

one is used to  mark bits that have mod 3 = 1.

two is used to mark bits that have mod 3 = 2.

Hope that helped!