1 Like
It is easy to see that the best position will be the highest power of 2 less than or equal to the input number. The numbers eliminated in the first pass will be the numbers whose 1st bit from the right is 1. In the second pass, the numbers whose 2nd bit from the right is 1 and so on. So the surviving number will be the one which has a 1 bit followed by as many 0 bits as possible or equivalently the highest power of 2 less than or equal to the input number.
2 Likes
http://ideone.com/HfYfAR here is the solution link.
As we can see everytime the answer will be highest power of two less than or equal to the input number. we can calculate y=(long int)log2(x). then answer=2y.
Enjoy.
2 Likes