one line java solution based on Josephus Problem


  • 11
    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


Log in to reply
 

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