Very efficient solution for P2 Elimination Game


  • 3

    Based on this solution by @NathanNi. Set all even bits lower than n's high-bit (corresponds to his adding of step in case of left), and keep the odd bits lower than the high-bit (corresponds to his adding of step in case of remaining % 2 == 1). My m is the bitmask of all bits lower than n's high-bit.

    int lastRemaining(int n) {
        int m = n >> 1;
        m |= m >> 1;
        m |= m >> 2;
        m |= m >> 4;
        m |= m >> 8;
        m |= m >> 16;
        return 1 + (0x55555555 & m | n & m);
    }
    

    Also check out @stachenov's awesome Java one-liner below.


  • 0

    @StefanPochmann as usual you're amazing :D


  • 1

    This. Is. Awesome. Seriously, this may very well qualify as the most awesome solution ever on LeetCode.

    Here is the same thing as a Java one-liner:

    return 1 + ((Integer.highestOneBit(n) - 1) & (n | 0x55555555))


  • 0

    @stachenov Darn, I don't feel bad about not knowing Integer.highestOneBit, but I should've used the distributivity. Very nice.


Log in to reply
 

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