We are going to understand this problem using the example given in figure 1.

The figure 1 shows the elements of an array and their bit representation.

Reader, notice in the array [51,57,51,57,63,38,57,63,63,51] , the number '38' is the only element marked in yellow. Hence it is our desired answer.

We have written the positions of the bits from 1 to 6 on top of all the elements. We count the number of 1s that occur at all the position and write them at the bottom. For example, for the 6 th position, the 1s occur a total of 10 times.

We put this count of 1s at all positions and the bit representation of '38' together and try to figure out a relation between them.

We realize that when the count at a position is of type 3n+1 like 10=3*3+1, 4=3*1+1 and 7=3*2+1, at those places the bit value is 1 (or "ON").

And the places at which count is of type 3n like 9=3*3 and 6=3*2 , there bit value is 0 (or "OFF").

Hence, the approach of solving this problem is to count the total 1 bits at each place. If at any position the count is of type 3n we put a 0 and if it is of type 1, we put a 1 against that position. After doing this process for all the positions, we find our desired number "100110".

We have learnt the approach; now let's discuss "WHY" this approach actually works.

Reader, notice at position 2, the contribution of all the numbers repeating three times is the same.

In the count at the second position excluding the bits of the number 38, we see that, 51 contributes 3 ones, 57 contributes 3 zeroes and 63 contributes 3 ones again. This gives us, 3+0+3=6. Hence, excluding the non repeating number we will always get a multiple of 3 i.e. 3n.

So if we now include the non-repeating number, then if 0 occurs at any position, the count remains a multiple of 3 i.e. 3n like we discussed and if 1 occurs at any position, the count becomes one more than the multiple of 3 i.e. 3n+1.

Reader, we want you to pay close attention to this other smarter approach of solving this problem.

We consider variables 3n, 3np1 and 3np2 which denote the multiples of 3, the multiples of 3n plus 1 and the multiples of 3n plus 2 respectively.

• We consider the first 3 elements and write the count of 1s at the respective positions. For, 51, 57 and 51, the count is 3-3-1-0-2-3.
• For 3n variable, we make those places as ON which are of type 3n at corresponding places in 3-3-1-0-2-3 and the rest of the places are considered as OFF.
  Hence, for 6th position, count=3 which is of type 3n, therefore under the variable 3n at the 6 th position, we put 1.
  But for 4 th position, count=1 which not of type 3n, therefore we put 0 at the corresponding place under the 3n column.
• Similarly, for 3np1, we make those places as ON which are of type 3n+1 for the count 3-3-1-0-2-3 and the rest of the places are considered as OFF.
  Hence, for 4 th position, count=1 which is of type 3n+1, therefore under the variable 3np1 at the 4 th position, we put 1.
  But for 2 nd position, count=2 which not of type 3n+1, therefore we put 0 at the corresponding place under the 3np1 column.
• The same concept is followed for 3np2.
• The way we have followed the above process for the first 3 elements, the same way we follow it for every element as discussed further.
• We initialize the values of 3n, 3np1 and 3np2 with 111111, 000000 and 000000 respectively.
• In 3np1 and 3np2 all digits are marked 0 because we haven't checked any of the digits yet.
• Now, we consider the bit representation of the 1 st element i.e. 110011.
• Next, we find out the common bits of 110011 with 3n, 3np1 and 3np2 as seen in figure 4.

• For 3n
  If at a place in 110011, the bit 1 is common with a bit of 111111, then it is represented by 1 and if they are not, it is represented by 0.
  Reader, meditate on the fact that finding the common bits of the 2 numbers is the same as the Bitwise Add (&) operation.
• For 3np1
  If at a place in 110011, bit 1 is common with a bit of 000000, then it is represented by 1 else we put 0 at the place.
  In this example, for 000000, there is no bit 1 present, therefore, no bit 1 of 110011 is common with it. Hence we again get 000000.
• For 3np2
  Similar to 3np1, if at a place in 110011, bit 1 is common with a bit of 000000, then it is represented by 1 else we put 0 at the place.
  In this example, in 000000, since there is no bit 1 present, therefore, no bit 1 of 110011 is common with it. Hence we again get 000000.
• We want you to watch the solution video [18:03-36:58] to understand how these common numbers are used.

For the above process, the following property is the essence.

We now write the code for this second approach. If you have understood the approach well, then you will have no problem in coding it.