C++ O(log n) non-recursive solution using bitwise operation


  • 0
    U

    Basic idea:

    • Every time we just cross off all the numbers with 0 or 1at the i-th bit under binary representation.
    • We just need to determine whether it's 0 or 1.
      Example: n=9=(1001)
      First iteration: 2, 4, 6, 8 All the remaining numbers has 0 at the least significant bit under binary representation
      Second iteration: 2, 6 All the remaining numbers has 1 at the second least significant bit under binary representation
      ...
    • How to determine whether it's 0 or 1? Has something todo with:
      (i)whether we know all the numbers remaining has a common 1 in some bits -- correspond to pos in my solution
      (ii) whether we're crossing off numbers from the beginning or the end -- correspond to flip in my solution
    class Solution {
    public:
        int lastRemaining(int n) {
            int ans = 0;
            int flip = 0;
            int power = 1;
            while (n > 1) {
                int pos = (ans > 0);
                int tmp = n & 1;
                ans |= (((1 ^ tmp) & flip) ^ pos) * power;
                n >>= 1;
                power <<= 1;
                flip ^= 1;
            }
            if (!ans)
                ans |= power;
            return ans;
        }
    };
    

Log in to reply
 

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