@Anonymous: There are 6 numbers in the list. The low order bit of
1^2^3^4^5^6 is 1. The low order bits of the input are 0,1,0,1,1,0. As
you read them, make a list pointers to the numbers that have low order
bit 0 and another list of pointers that have low order bit 1, and also
take their exclusive or: 0^1^0^1^1^0 = 1. This equals the xor of the
low order bit, so the low order bit of the result is 0.
Now, consider only the numbers in the "0 as a low-order bit" list: 0,
2, 6. There are 3 numbers in the list, and 1^2^3 = 0. Their second
bits are 0,1,1, and the xor is 0. As you read the numbers, make
sublists of the 0s and the 1s. Since the two xors are equal, the
second bit of the result is 0.
Now, consider only the numbers in the "0 in the second bit" list: 0.
There is 1 number in the list so the xor of the number of numbers is
1. The xor of the third bit of the data is 0. Since these numbers
disagree, the result is that the third bit is 1.
Thus, the missing number has binary representation 100, which is 4.
Hope this helps.
Dave
On Jul 12, 6:39 am, anonymous procrastination <opamp1...@gmail.com>
wrote:
> @Dave
> Can you please explain through example.
> Suppose the set is {0,1,2,3,5,6}
> Then how this solution proceeds.
> I am partially getting the logic you explained but need to see an
> example.
>
> Thanks!!
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
