The list is a arithmetic progression.

It can be represent by a vector v = (S, N, D). S means the value of first element, N means number of element in this list, D means difference between the consecutive elements.

So the original list is (S=1,N=n,D=1).

After each elimination, the list will remain a arithmetic progression. N will be N/2; D will be 2*D; S will be S or S+D;

class Solution {

public:

int lastRemaining(int n) {

int D(1);

int S(1);

bool forward(true);

while (n > 1) {

if (forward) {

S += D;

} else {

if (n&1) {

S += D;

}

}

n >>= 1;

forward = !forward;

D <<= 1;

}

return S;

}

};