# one line java solution based on Josephus Problem

• This problem is similar to Josephus problem when k=2, the recursive version is easy after referring to the josephus problem on wiki.
it is highly recommend to refer to Josephus problem first, because i am chinese, my english is poor, my explanation may not be good, but the wiki explanation is very good.

``````    public int lastRemaining(int n) {
return ((Integer.highestOneBit(n) - 1) & (n | 0x55555555)) + 1;
}
``````

recursive version
for example:
1,2,3,4,...n
if you start from the left to right, the result is i
then, if you start from right to left, the result is n+1-i
for n numbers, after one pass, there are n/2 left, each number is two times of the original,
1,2,3,4,5,6,7,8,9
after one pass
2,4,6,8
assume the result of 1,2,3,4 from left to right is f(4)
then the result of 1,2,3,4 from right to left is 5-f(4)
then the result of 2,4,6,8 from right to left is 2*(5-f(4))
this is the formula
f(n)=2(1+n/2-f(n/2))* when n is 1, of course the result is 1

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

non-recursive version:

``````    public int lastRemaining(int n) {
Stack<Integer> stack = new Stack<>();
while (n > 1) {
n /= 2;
stack.push(n);
}
int result = 1;
while (!stack.isEmpty()) {
result = 2 * (1 + stack.pop() - result);
}
return result;
}
``````

• This O(1) solution enlightened by Josephus Problem is really outstanding!

• public int lastRemaining(int n) {
return ((Integer.highestOneBit(n) - 1) & (n | 0x55555555)) + 1;
}
I read and understood Josephus problem but how did you incorporate alternate left and right direction and came up with this solution? Can you pls explain. Thanks

• you explained it very well. :)

• You should probably explain the first code snippet a bit better. `0x55555555`
is basically a 'magic number' that your readers won't understand. Short code is probably better for competitions, not in this context where your code is meant to be understood :)

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