Python 3 solution for https://leetcode.com/problems/elimination-game

eliminationgame.py

class Solution:
	def lastRemaining(self, n):
		"""
		:type n: int
		:rtype: int
		"""
		odd = True
		remainder = n
		startNum = 1
		power = 1

		while remainder > 1:
			if remainder == 2:
				return startNum+power if odd else startNum
			elif remainder == 3:
				return startNum+power

			# startNum increases only by 2 case, if the remainder is odd OR if the step is odd
			startNum += power if remainder % 2 == 1 or odd else 0	
			power *= 2

			# Divide by 2 and floor
			remainder //= 2
			odd = not odd

		# n == 1 returns 1
		return 1

Space complexity: O(1)
Time complexity: O(log n)