Skip to content

390. Elimination Game

  • Time: $O(\log n)$
  • Space: $O(\log n)$
1
2
3
4
5
6
class Solution {
 public:
  int lastRemaining(int n) {
    return n == 1 ? 1 : 2 * (1 + n / 2 - lastRemaining(n / 2));
  }
};

1
2
3
4
5
class Solution {
  public int lastRemaining(int n) {
    return n == 1 ? 1 : 2 * (1 + n / 2 - lastRemaining(n / 2));
  }
}

1
2
3
class Solution:
  def lastRemaining(self, n: int) -> int:
    return 1 if n == 1 else 2 * (1 + n // 2 - self.lastRemaining(n // 2))