# 390. Elimination Game

There is a list of sorted integers from 1 to  n. 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 right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length  n.

Example:

``````Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

Output:
6
``````

``````class Solution {
public:
int lastRemaining(int n) {
return help(n, true);
}
int help(int n, bool left2right) {
if (n == 1) return 1;
if (left2right) {
return 2 * help(n / 2, false);
} else {
return 2 * help(n / 2, true) - 1 + n % 2;
}
}
};
``````

``````class Solution {
public:
int lastRemaining(int n) {
return n == 1 ? 1 : 2 * (1 + n / 2 - lastRemaining(n / 2));
}
};
``````

n = 8
1 2 3 4 5 6 7 8
2    4    6   8
2          6
6

n = 7
1 2 3 4 5 6 7
2    4    6
4

``````class Solution {
public:
int lastRemaining(int n) {
int step = 1, res = 1;
while (step * 2 <= n) {
res += step;
step *= 2;
if (step * 2 > n) break;
if ((n / step) % 2 == 1) res += step;
step *= 2;
}
return res;
}
};
``````

``````class Solution {
public:
int lastRemaining(int n) {
bool left2right = true;
int res = 1, step = 1, remain = n;
while (remain > 1) {
if (left2right || remain % 2 == 1) res += step;
remain /= 2;
step *= 2;
left2right = !left2right;
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/390

https://leetcode.com/problems/elimination-game/

https://leetcode.com/problems/elimination-game/discuss/87128/C-1-line-solution-with-explanation

https://leetcode.com/problems/elimination-game/discuss/87121/O(logN)-solution.-clear-break-down

https://leetcode.com/problems/elimination-game/discuss/87120/one-line-java-solution-based-on-Josephus-Problem

https://leetcode.com/problems/elimination-game/discuss/87119/JAVA%3A-Easiest-solution-O(logN)-with-explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation