@zhiqing_xiao: Thank you for your answer. I had a quick question. You say that in the second pass, the two numbers identified in the first pass fall into two distinct groups. In order to do this, we identify the rightmost bit (in your example) and use it to identify in which of the two groups the numbers will fall.
However, what if in both the numbers the same right-most digit is set? For e.g., in case of 3, the rightmost set bit is at location 0 and so is the case with 5. So, wouldn't they both fall in the same groups? We need to find out the next set bit (to the left of the current one) then. Is my understanding correct?
Thanks, I appreciate your help!
Edit: On walking through the code again, I understood my mistake. We are not XORing the two numbers - we XOR one of the numbers with the total XOR of the array. Hence, the above problem of 3 and 5 both having last set bit at the same location does not occur!