Find the winner of the circular game

September 29, 2022

queue

Problem URL: Find the winner of the circular game

We can use a queue and add all the numbers to the queue and then remove every kth element. Then when just one item is left in the queue, we return that item.

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        q = collections.deque(range(1, n+1))
        while len(q) > 1:
            for _ in range(k-1):
                q.append(q.popleft())
            q.popleft()
        return q[0]

Time Complexity: O(n*k)
Space Complexity: O(n)