# 3 lines Iterative code in Python, O(log N), O(1) space

• Basically we calculate the next starting point, and we go forward and backwards each time.
Step gets multiplied by two at each loop iteration.
Complexity is θ(log N) because we divide n by 2 at each iteration. Size complexity is O(1).

``````class Solution(object):
def lastRemaining(self, n):
start, size, inv = 1, 1, 1
while n > 1: start, size, inv, n = start + inv * size + 2 * (n // 2 - 1) * inv * size,\
size * 2, inv * -1,\
n // 2
return start
``````

Here's my 4-line O(n) O(n) code that didn't get accepted:

``````class Solution(object):
def lastRemaining(self, n):
def game(nums):
if len(nums) <= 1: return nums[0]
return game([nums[i] for i in range(1, len(nums), 2)][::-1])
return game([i for i in range(1, n + 1)])
``````

• Bit shorter code for the second "solution":

``````def lastRemaining(self, n):
def game(nums):
return nums[0] if len(nums) == 1 else game(nums[1::2][::-1])
return game(range(1, n + 1))
``````

But I think iterative looks nicer

``````def lastRemaining(self, n):
nums = range(1, n+1)
while len(nums) > 1:
nums = nums[1::2][::-1]
return nums[0]``````

• @StefanPochmann Nice, forgot to use `nums[1::2]`.

• @livelearn I know. @agave had already said "didn't get accepted" and I put "solution" in quotes because of this.

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