LC-1823 Medium LeetCode

1823. Find the Winner of the Circular Game

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 82% Topics: Array, Math, Recursion, Queue, Simulation

Reading material

Arrays & Hashing 12 min Math & Geometry 12 min Backtracking 14 min

Reference solution (spoiler · python)

# 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

Solution from kamyu104/LeetCode-Solutions · MIT