Find the Losers of the Circular Game — LeetCode 2682 Python Solution

The problem

There are n friends that are playing a game. The friends are sitting in a circle and are numbered from 1 to n in clockwise order.

Example

Input

n = 5, k = 2

Output

[4,5]

Explanation

The game goes as follows:

Python solution

class Solution:
    def circularGameLosers(self, n: int, k: int) -> List[int]:
        vis = [False] * n
        i, p = 0, 1
        while not vis[i]:
            vis[i] = True
            i = (i + p * k) % n
            p += 1
        return [i + 1 for i in range(n) if not vis[i]]

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 2682. Find the Losers of the Circular Game is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems