Find the Survivor of Alternating Eliminations
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Find the Survivor of Alternating Eliminations
Start with the increasing list `[1,2,...,n]`.
In the first pass, scan left to right, removing the first number and every other number after it. In the next pass, scan the remaining list right to left, removing the rightmost number and every other number after it in that direction.
Keep alternating directions until one number remains. Return that number.
### Function
`int lastRemaining(int n)`
### Example 1
```text
Input: n = 10
Output: 8
```
The successive remaining lists are:
```text
[1,2,3,4,5,6,7,8,9,10]
[2,4,6,8,10]
[4,8]
[8]
```
### Example 2
```text
Input: n = 6
Output: 4
```
### Example 3
```text
Input: n = 1
Output: 1
```
### Constraints
- `1 <= n <= 1000000000`.
### Clarifications
Every pass starts by removing the first number encountered in its own direction. Alternate directions between passes, not between individual removals. If the starting list already has one number, no pass is needed.
### What a Strong Answer Covers
- Exact elimination order in both directions.
- Odd and even remaining-list sizes.
- Correctness and time/storage bounds for large `n`.
Overview: Practice determining the final survivor when alternate elements are removed in alternating directions. Preserve pass order and handle odd and even list sizes.