# O(logN) solution. clear break down

• ``````    public int lastRemaining(int n) {
return leftToRight(n);
}

private static int leftToRight(int n) {
if(n <= 2) return n;
return 2 * rightToLeft(n / 2);
}

private static int rightToLeft(int n) {
if(n <= 2) return 1;
if(n % 2 == 1) return 2 * leftToRight(n / 2);
return 2 * leftToRight(n / 2) - 1;
}
``````

• @beijunyi Easy to understand, thanks for sharing.

• Clever use of mutual recursion, almost self-explained! I reduce the base case a little bit and add some comments for easier understand.

``````    public int lastRemaining(int n) {
return leftToRight(n);
}

// eliminate [1...n] first from left to right, then alternate
private int leftToRight(int n) {
if (n == 1) return 1;
// scan from left to right is simple, the length of array doesn't matter
// [1, 2, 3, 4] -> 2 * [1, 2]
// [1, 2, 3, 4, 5] -> 2 * [1, 2]
return 2 * rightToLeft(n / 2);
}

// eliminate [1...n] first from right to left, then alternate
private int rightToLeft(int n) {
if (n == 1) return 1;
// if the length of array is even, we will get only odd number
// [1, 2, 3, 4] -> [1, 3] = 2 * [1, 2] - 1
if (n % 2 == 0) return 2 * leftToRight(n / 2) - 1;
// else if the length of array is odd, we will get only even number
// [1, 2, 3, 4, 5] -> [2, 4] = 2 * [1, 2]
else return 2 * leftToRight(n / 2);
}
``````

• This post is deleted!

• It took me some time to fully understand this recursive approach, but I think this is a great solution! Here is a very detailed explanation if anyone is wondering:

Denote `L` as traversing `[1,...,n]` from left to right, `R` as traversing `[1,...,n]` from right to left.

• When n is odd:
`L(1234567) = R(246) = R(123)*2`
`R(1234567) = L(246) = L(123)*2`

• When n is even:
`L(123456) = R(246) = R(123)*2`
`R(123456) = L(135) = L(123) + 1` (a bit tricky)

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