C++ plus some math, O(logN), but maybe not the best


  • 0
    L
    class Solution {
    public:
    	int lastRemaining(int n) {
    
    		int bitmask = 0x01;
    		int comparemask = 0x01;
    		int cnt = n--;
    		int isEven = 0xFFFFFFFF;
    		int res = 0x0;
    
    		for (; cnt > 1;) {
    			res = res | bitmask & (isEven | ~n);
    
    			while (comparemask & (res ^ n))
    				n--;
    			bitmask = bitmask << 1;
    			isEven = ~isEven;
    			comparemask = comparemask | bitmask;
    			cnt /= 2;
    		}
    		return n + 1;
    	}
    };
    

    If we substract 1 from every number, we may find that everytime we eliminate from the left, we eliminate every number whose 2k bit (from low to high, starting from 0) is not 0, like 00000010, 00001001 and so on. Then I use some simulating method to "eliminate from the right"


Log in to reply
 

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