one line java solution based on Josephus Problem


  • 12
    F

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

  • 0
    W

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


  • 0
    J

    @fhqplzj said in one line java solution based on Josephus Problem:

    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


  • 0
    S

    you explained it very well. :)


  • 0
    D

    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 :)


Log in to reply
 

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