C 1 line solution with explanation


  • 58
    Z

    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));
    }
    

  • 5
    S

    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.


  • 1

    really like it :DDD


  • 0
    P

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


  • 14
    Z

    @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).


  • 0

    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.


  • 0
    R

    Very brilliant solution. Thanks


  • 0
    T

    Marvelous Solution!!!


  • 0
    X

    @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


  • 0
    A

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


Log in to reply
 

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