Hey there coder. We are going to discuss a new question under Bit Manipulation called "All Repeating Three Times Except One".
Important Link : Problem Link , Solution Video Link
All Repeating Three times except One
The best error message is the one that never shows up.
~Thomas Fuchs
Hey there coder. We are going to discuss a new question under Bit Manipulation called "All Repeating Three Times Except One".
Important Link : Problem Link , Solution Video Link
We want you to go through the outline of the problem first to understand it better.
For example, if the input array is [2,2,1,3,2,3,3], then we required to print '1' because all other numbers except '1' occur thrice in the array.
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.
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.
java; true";
O(n)
O(1)
Reader, we have now reached the end of our discussion. In case you were not able to understand any part of this article, we highly suggest you to watch its solution video.