308. Left-Right Elimination
Contestants numbered 1, 2, ..., n stand in a row for a sweeping elimination game. In the first sweep a referee walks from the left end to the right end and sends home the first contestant and then every second contestant after that. In the next sweep the referee walks from the right end to the left and again sends home the contestant at the end he starts from and every second one after that.
The sweeps keep alternating direction, always working on the contestants still in the row, until a single contestant is left. Given n, return the number of the last remaining contestant. Simulating every sweep is far too slow for a billion contestants, so look for a relation between the answer for n and the answer for about half as many.
Example 1
- Input:
- n = 9
- Output:
- 6
- Explanation:
Sweep one removes 1, 3, 5, 7, 9 leaving 2, 4, 6, 8. The right-to-left sweep removes 8 and 4 leaving 2, 6. The next sweep removes 2, so 6 survives.
Example 2
- Input:
- n = 10
- Output:
- 8
- Explanation:
Sweep one leaves 2, 4, 6, 8, 10. The right-to-left sweep removes 10, 6 and 2 leaving 4, 8. Then 4 is removed and 8 survives.
Constraints
1 ≤ n ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log n)
- Space
- O(log n)