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


  • 1

    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)])
    

  • 3

    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]

  • 0

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


  • 0
    L

  • 0

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


Log in to reply
 

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