Medium
Quiz
#390 Elimination Game
APPROACH
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
1 of 4
1:00
What is the optimal approach for this problem?