C 1 line solution with explanation

• After first elimination, all the numbers left 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));
}
``````

• Great answer. In fact, we can prove that "ML(1...n) + MR(1...n) = 1 + n" holds for any n >= 2, where ML(1...n) means removing elements from left to right first and MR(1...n) means removing elements from right to left first.

• really like it :DDD

• Could you explain the meaning of (1 + n / 2 - lastRemaining(n / 2))? Thank you very much.

• @pkuzw Actually you can refer to @storypku 's answer on the 1st floor. It's called mirroring. Given a sequence 1, 2, 3,...N, first we can easily know that 1 and N are mirrored by the middle of this sequence, and it holds for (2, N-1), (3, N-2) and so on. Sum of them are all N+1.

Then we come to the problem, suppose we have two rules: (1) the first elimination starts from the left side; (2) the first elimination starts from the right side. We follow the same elimination rules it's just the starting point is mirrored by the center. So we have:

lastRemaining(n) + EliminateFromRightFirst(n) = n + 1;
<=> lastRemaining(n/2) + EliminateFromRightFirst(n/2) = n/2 + 1;
<=> EliminateFromRightFirst(n/2) = 1 + n/2 - lastRemaining(n/2);

For the original sequence 1,2,3,...,n, after first elimination from left side, we have a new sequence 2,4,6,...,(n-1 or n). The new sequence consists of even numbers. Then actually it is 2 * (1, 2, 3, ..., n/2), in which the elimination for the (1, 2, 3, ... n/2) now starts from the right side. It is exactly EliminateFromRightFirst(n/2).

• Same idea.

The key point here is calculate what''s the index of the final remaining number (given the numbers indexed from 1 to n) instead of the number.

• Very brilliant solution. Thanks

• Marvelous Solution!!!

• @zhangyiwei 's solution is great and the core idea is to find that `ML(1..n) + MR(1..n) = 1 + n` which is mentioned by @storypku.
Here I gave a simple proof of the equation if it can help.
Suppoese `ML(1...n) = r`;
We can replace each element in array `1...n` by `newValue = (n + 1) - oldValue` to get a new array `n...1`;
Then we can easily find the result of `MR(n...1) = r` also;
Consider the the location of `r` in array `n...1`, it should be the same with the location of the result of `MR(1...n)` since following the same elimination rule;
Then the corresponding value of `r` in array `1...n` should be `(n + 1) - r`, which gives the result of `MR(1...n)`.
This proves `ML(1..n) + MR(1..n) = 1 + n`

• Although the space complexity is O(logn), the thinking is genius!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.