find-the-winner-of-the-circular-game.py

# Time:  O(n)
# Space: O(1)

# bottom-up solution
class Solution(object):
    def findTheWinner(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: int
        """
        return reduce(lambda idx, n:(idx+k)%(n+1), xrange(1, n), 0)+1


# Time:  O(n)
# Space: O(n)
# top-down solution
class Solution2(object):
    def findTheWinner(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: int
        """
        def f(idx, n, k):
            if n == 1:
                return 0
            return (k+f((idx+k)%n, n-1, k))%n
        
        return f(0, n, k)+1