## Monday, August 29, 2016

### Leetcode 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```

def lastRemaining(self, n): """ :type n: int :rtype: int """ a = p = 1 cnt = 0 while n > 1: n /= 2 cnt += 1 p *= 2 if cnt % 2: a += p / 2 + p * (n - 1) else: a -= p / 2 + p * (n - 1) return a

http://zyy1314.com/2016/08/28/leetcode390/

1. 当我们从左边开始遍历删除元素时
2. 当我们从右边开始遍历元素，并且剩下的数组元素个数为奇数时

2,4,6,8,10

2,4,6,8,10,12

```
public int lastRemaining(int n) {

boolean left = true;

int remain = n;

int step = 1;

int head = 1;

while(remain>1){

if(left||remain%2==1){

}

remain /=2;

left =!left;

step *=2;

}

}
```

https://segmentfault.com/a/1190000006739199
``````    public int lastRemaining(int n) {
int rest = n, start = 1, step = 2;
boolean left = true;
while (rest > 1) {
rest /= 2;
if (left) start = start + step * rest - step / 2;
else start = start - step * rest + step / 2;
step *= 2;
left = !left;
}
return start;
}``````
X. Recursive
https://discuss.leetcode.com/topic/58042/c-1-line-solution-with-explanation
After first elimination, all the rest numbers are even numbers.
Divide by 2, we get a continuous new sequence from 1 to n / 2.
For this sequence we start from right to left as the first elimination.
Then the original result should be two times the mirroring result of lastRemaining(n / 2).
``````int lastRemaining(int n) {
return n == 1 ? 1 : 2 * (1 + n / 2 - lastRemaining(n / 2));
}
``````

http://www.cnblogs.com/grandyang/p/5860706.html

```    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 1 + n - 2 * (1 + n / 2 - help(n / 2, true));
}
}```

http://codefang.blogspot.com/2016/08/leetcode-weekly-contest390-elimination.html