# [390. Elimination Game](https://leetcode.com/problems/elimination-game/)


## 题目

You have a list `arr` of all integers in the range `[1, n]` sorted in a strictly increasing order. Apply the following algorithm on `arr`:

- Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
- Repeat the previous step again, but this time from right to left, remove the rightmost number and every other number from the remaining numbers.
- Keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Given the integer `n`, return *the last number that remains in* `arr`.

**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

```

**Constraints:**

- `1 <= n <= 109`

## 题目大意

列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。请你对 arr 应用下述算法：

- 从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。
- 重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。
- 不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。

给你整数 n ，返回 arr 最后剩下的数字。

## 解题思路

- 模拟题。按照题意，第一轮从左往右删除数字，第二轮从右往左删除数字。题目要求最后剩下的数字，模拟过程中不需要真的删除元素。只需要标记起始元素，该轮步长和方向即可。最后总元素只剩下一个即为所求。

## 代码

```go
package leetcode

func lastRemaining(n int) int {
	start, dir, step := 1, true, 1
	for n > 1 {
		if dir { // 正向
			start += step
		} else { // 反向
			if n%2 == 1 {
				start += step
			}
		}
		dir = !dir
		n >>= 1
		step <<= 1
	}
	return start
}
```