I spent a long long time trying to see if there was some kind of pattern to follow, but I just couldn't seem to find anything concrete. Really curious how people approached it  I tried brute forcing it, and had an O(n) solution, but that TLE and too much memory. Was there some kind of trick that I was missing??
Problem 2? How'd people approach it?


the complexity could be O(logn)
use two indices to record the edge of unexplored numbers.
and use a counter to record the number of visited numbers.the trick is you do not need to actually visit each number, you can find the number of numbers you would visit in certain pass by
(rightleft)/step + 1class Solution { public: int lastRemaining(int n) { int count = 0, step = 2, left = 1, right = n; while(count < n) { if(count==n1) return right; count += (rightleft)/step+1; if((rightleft)%step==0) right = step/2; left += step/2; if(count==n1) return left; step *= 2; count += (rightleft)/step+1; if((rightleft)%step==0) left += step/2; right = step/2; if(count==n1) return right; step *= 2; } return left; } };

A pattern can be easily found if we do every elimination from left: the remaining numbers can only be powers of 2. For one elimination from right and the length of current array is not odd (otherwise it will be equivalent to elimination from left), the pattern is still there, only with some shift.
class Solution { public: int lastRemaining(int n) { if (n < 1) return 0; if (n == 1) return 1; int mul = 1, shift = 0; while (n != 1) { n /= 2; mul *= 2; if (n == 1) break; if ((n & 1) == 0) shift = mul; n /= 2; mul *= 2; } return mul + shift; } };

Here's my recursive solution
 If eliminate from left
[1...2n+1] > [2,4,6,...2n] = 2 * [1...n]
[1...2n+0] > [2,4,6,...2n] = 2 * [1...n]  If eliminate from right
[1...2n+1] > [2,4,6,...,2n] = 2 * [1...n]
[1...2n+0] > [1,3,5,...,2n1] = 2 * [1...n]  1
class Solution { public: int lastRemaining(int n, bool fromLeft) { if(n <= 1) { return 1; } if(fromLeft) { return 2 * lastRemaining(n / 2, false); } else { if(n & 1) { return 2 * lastRemaining(n / 2, true); } else { return 2 * lastRemaining(n / 2, true)  1; } } } int lastRemaining(int n) { return lastRemaining(n, true); } };
 If eliminate from left

We only need the left, right and step to decide the left, right and step of the next iteration:
class Solution { public: int lastRemaining(int n) { int left = 1; int right = n; int t = 1; while (right > left) { if (((right  left) / t) % 2 == 0) right = t; left += t; t *= 2; if (left >= right) return left; if (((right  left) / t) % 2 == 0) left += t; right = t; t *= 2; } return left; } };

I got TLE too, even though I was thinking “What on earth am I doing” when clicking the Submit button. Really, it was pretty obvious that I only get penalty time this way. Must be because it was 4:30 a. m. here.
Then I found a pretty elegant solution. At first, we remove all odd numbers, so the resulting sequence can be expressed as
2k + 2
wherek = 0, 1, 2...
Generalizing that, I figure that it must bea * k + b
after every iteration, wherea
andb
are some integers. The trick is, then, to update thosea
andb
on each iteration. Note thatb
is the first number in the sequence.If we're going lefttoright, then
b
increases bya
. That's because we're striking out the first number (withk == 0
), so the first remaining one will bea * 1 + b
.If we're going righttoleft, then
b
only increases bya
if we end up striking out the first (the last from the right) number. That happens only if the number of numbers is odd. Otherwiseb
is unchanged.As for
a
, it just doubles on every iteration. It's that simple. The total number of numbers just halves (round down).That gave me a very simple algorithm:
 Initialize
a = 1
,b = 1
.  While there are more than one number remaining repeat the following:
 If going lefttoright or if the number of remaining numbers is odd, increase
b
bya
.  Double
a
.  Half the number of numbers.
 Reverse the direction and repeat.
 When the loop is over, return
b
.
The code in Java:
public int lastRemaining(int n) { int a = 1, b = 1; // 1k + 1 int m = n; boolean ltr = true; while (m > 1) { if (ltr  (m & 1) == 1) { b += a; } a *= 2; m /= 2; ltr = !ltr; } return b; }
 Initialize