Only 3 lines, C++, O(logN)


  • 2
    Y
    class Solution {
    public:
        int lastRemaining(int n) {
            int tmp = 0x7FFFFFFF;
            while(tmp >= n) tmp >>= 1;
            return  ((n|0x55555555)&tmp) + 1;
        }
    };
    

  • 0

    That should be explained.


  • 0

    @YLAsce Can you explain? Looks like black magic to me.


  • 1
    G

    You can get that solution mentioned at the top by optimizing this solution:

    class Solution {
    public:
        int lastRemaining(int n) {
            bool keepSingle = true;
            unsigned int res = 0;
            unsigned int mask = 1;
            while(n != 1) {
                if((n & 1) == 0) {
                    res += mask * (keepSingle ? 1 : 0);
                } else {
                    res += mask;
                }
                cout << res << " " << n << keepSingle << endl;
                keepSingle = !keepSingle;
                mask <<= 1;
                n >>= 1;
            }
            
            return res + 1;
        }
    };
    

    You can optimize it by "vectorization".
    So, the vectorized version of keepSingle is 0x55555555. And here is my final solution:

    class Solution {
    public:
        int lastRemaining(int n) {
            unsigned int res = 0x55555555;
            unsigned int mask = 0;
            unsigned int m = n;
            while(n != 1) {
                mask <<= 1;
                mask |= 1;
                n >>= 1;
            }
            return ((res | m) & mask) + 1;
        }
    };
    

Log in to reply
 

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