#390
Elimination Game
specialist · 970 · lc medium +32 · verified · 46% accepted · 1,732 likes · top 30%
Description
Start with the list arr = [1, 2, ..., n] and repeatedly eliminate elements using alternating passes until exactly one element survives:
- On a left-to-right pass: remove the leftmost element, then every other remaining element.
- On a right-to-left pass: remove the rightmost element, then every other remaining element.
- Alternate directions with each pass.
Given n, return the last surviving element.
Example 1:
Input: n = 9
Output: 6
Explanation:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr = [2, 4, 6, 8]
arr = [2, 6]
arr = [6]
Example 2:
Input: n = 1
Output: 1
Code
1
2
3