MOVQUE – Editorial
#PROBLEM LINK:Practice : Click
Contest : Click
Author: Soham Chakrabarti
#PREREQUISITES:Human Brain, Time to think
#PROBLEM:Chef loves to watch movies.
But unfortunately, when he goes to buy the tickets, only one ticket is left.
There are N people standing in line, in front of the booking office and everyone wants the ticket.
Only one can get the ticket.
The Rule is:
- People standing in the even position of the line (2nd, 4th,…) forms another line.
The line is from 1 to N( for this problem).
The rule is repeated until, one remains.
Help chef stand in the correct spot and get the movie ticket.
#QUICK EXPLANATION:We can solve this problem by simple math. All we need to observe is that, the even positions are getting fetched every single time. Therefore, all we need to find is the Nearest power of 2, which is less than or equal to N.
#EXPLANATION:Everytime, we get the even positions from the Queue. Thus, it means:
1 2 3 4 5 6 7 8 9
–> 2 4 6 8
If you observe carefully, it took exactly 3 steps to get the exact position of the spot, that brings you to the theatre. If you check out with all the other values of N, you will notice that the number of times, the queue breaks and makes itself, is the power of 2.
Here pow(2,3) = 8.
Thus, we can conclude, it will always end up with the nearest power of 2, less than or equal to N.