LeetCode 2682 - Find the Losers of the Circular Game

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Simulation

Solution

Problem Understanding

This problem describes a circular passing game among n friends numbered from 1 to n. The ball always starts with friend 1, and each turn increases the number of clockwise steps by a multiple of k.

More specifically:

On the first turn, the current player passes the ball 1 * k steps clockwise.
On the second turn, the next player passes it 2 * k steps clockwise.
On the third turn, the next player passes it 3 * k steps clockwise.
This pattern continues until someone receives the ball for the second time.

The task is to determine which friends never receive the ball at all during the game. These friends are called the losers.

The input consists of:

n, the total number of friends sitting in a circle
k, the step multiplier used for each turn

The output should be a list of friend numbers, sorted in ascending order, representing all friends who never touched the ball.

Because the friends sit in a circle, movement wraps around. If we move beyond friend n, we continue again from friend 1. This is naturally handled using modulo arithmetic.

The constraints are very small:

1 <= k <= n <= 50

This tells us several important things:

Efficiency is not a major concern because the input size is tiny.
A direct simulation is completely acceptable.
We do not need advanced mathematical optimization.
We can safely track visited players using arrays or sets.

Some important edge cases include:

n = 1, where there is only one friend, meaning the game immediately ends.
k = n, where every move wraps around exactly to the same position.
Situations where only a small subset of players ever receives the ball.
Cases where the cycle repeats very quickly.

A naive implementation can easily make mistakes with indexing because the problem uses 1-based numbering while most programming languages use 0-based indexing internally.

Approaches

Brute Force Approach

The most direct solution is to simulate the game exactly as described.

We begin with friend 1 holding the ball. On each turn:

Mark the current friend as visited.
Compute the next friend using the current turn number and the step size k.
Continue until we reach a friend who has already received the ball.

At the end, every unvisited friend is a loser.

This approach is guaranteed to work because the game rules are deterministic. Since there are only n friends, eventually some friend must receive the ball again, causing the process to terminate.

Even though this is technically brute force simulation, the constraints are so small that it is already efficient enough.

Key Insight for the Optimal Solution

The key observation is that we only need to track which friends have already received the ball.

Because each friend can only be visited once before the game terminates, the simulation performs at most n iterations.

Using a boolean array or hash set allows us to:

Detect repeated visits efficiently
Mark players as visited in constant time
Collect unvisited players afterward

Thus, the optimal solution is simply a clean simulation with visited tracking.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Could repeatedly scan structures inefficiently
Optimal	O(n)	O(n)	Direct simulation with visited tracking

Algorithm Walkthrough

Create a boolean array called visited of size n, initialized to False.

This array records whether each friend has received the ball. Index 0 corresponds to friend 1, index 1 to friend 2, and so on. 2. Start with the current player at index 0.

Since friend numbering starts from 1, using index 0 internally simplifies modulo arithmetic. 3. Initialize the turn counter to 1.

The first pass moves 1 * k steps, the second pass moves 2 * k steps, and so forth. 4. Continue the simulation while the current player has not already been visited.

If we encounter a player who already received the ball, the game ends immediately. 5. Mark the current player as visited.

This records that the player has now received the ball. 6. Compute the next player using circular movement.

The formula is:

next_position = (current_position + turn * k) % n

The modulo operation ensures the movement wraps around the circle correctly. 7. Increment the turn counter.

Each round increases the distance by another multiple of k. 8. After the loop finishes, iterate through the visited array.

Every player whose value is still False never received the ball and is therefore a loser. 9. Return the list of losers in ascending order.

Since we iterate from left to right, the result is naturally sorted.

Why it works

The algorithm exactly follows the game rules. Each iteration simulates one pass of the ball. The visited array guarantees that we stop the moment a player receives the ball for the second time. Since every visited player is recorded precisely once, the remaining unvisited players are exactly the losers.

Python Solution

from typing import List

class Solution:
    def circularGameLosers(self, n: int, k: int) -> List[int]:
        visited = [False] * n

        current = 0
        turn = 1

        while not visited[current]:
            visited[current] = True

            current = (current + turn * k) % n
            turn += 1

        losers = []

        for i in range(n):
            if not visited[i]:
                losers.append(i + 1)

        return losers

The implementation starts by allocating a boolean array named visited. Each position corresponds to one friend.

The variable current stores the current player's index using 0-based indexing. The variable turn tracks how many passes have occurred so far.

The while loop continues as long as the current player has never received the ball before. Inside the loop, we first mark the player as visited. Then we compute the next position using the circular movement formula.

After the simulation ends, we iterate through all players and collect those who were never visited. Since indices are 0-based internally, we add 1 when constructing the final answer.

Go Solution

func circularGameLosers(n int, k int) []int {
    visited := make([]bool, n)

    current := 0
    turn := 1

    for !visited[current] {
        visited[current] = true

        current = (current + turn*k) % n
        turn++
    }

    losers := []int{}

    for i := 0; i < n; i++ {
        if !visited[i] {
            losers = append(losers, i+1)
        }
    }

    return losers
}

The Go implementation follows the exact same logic as the Python version.

A boolean slice is used for visited tracking. The result is stored in a dynamically growing slice named losers.

There are no integer overflow concerns because the constraints are extremely small. Go slices naturally handle dynamic appending, making result construction straightforward.

Worked Examples

Example 1

Input:

n = 5
k = 2

Initial state:

Variable	Value
current	0
turn	1
visited	[False, False, False, False, False]

Iteration 1

Current friend:

friend 1

Mark visited:

visited = [True, False, False, False, False]

Compute next position:

(0 + 1 * 2) % 5 = 2

Next friend is friend 3.

Update:

Variable	Value
current	2
turn	2

Iteration 2

Current friend:

friend 3

Mark visited:

visited = [True, False, True, False, False]

Compute next position:

(2 + 2 * 2) % 5 = 1

Next friend is friend 2.

Update:

Variable	Value
current	1
turn	3

Iteration 3

Current friend:

friend 2

Mark visited:

visited = [True, True, True, False, False]

Compute next position:

(1 + 3 * 2) % 5 = 2

Next friend is friend 3.

Update:

Variable	Value
current	2
turn	4

Now friend 3 has already been visited, so the game stops.

Unvisited friends are:

[4, 5]

Example 2

Input:

n = 4
k = 4

Initial state:

Variable	Value
current	0
turn	1
visited	[False, False, False, False]

Iteration 1

Current friend:

friend 1

Mark visited:

visited = [True, False, False, False]

Compute next position:

(0 + 1 * 4) % 4 = 0

The ball returns immediately to friend 1.

Since friend 1 is already visited, the game ends.

Losers:

[2, 3, 4]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each friend is visited at most once before the loop stops
Space	O(n)	The visited array stores one boolean per friend

The simulation terminates once a repeated player is encountered. Since there are only n players, the loop cannot execute more than n times. All operations inside the loop are constant time, giving an overall time complexity of O(n).

The only additional memory used is the visited array and the result list, both proportional to n.

Test Cases

from typing import List

class Solution:
    def circularGameLosers(self, n: int, k: int) -> List[int]:
        visited = [False] * n

        current = 0
        turn = 1

        while not visited[current]:
            visited[current] = True
            current = (current + turn * k) % n
            turn += 1

        return [i + 1 for i in range(n) if not visited[i]]

sol = Solution()

assert sol.circularGameLosers(5, 2) == [4, 5]  # Provided example
assert sol.circularGameLosers(4, 4) == [2, 3, 4]  # Immediate repeat
assert sol.circularGameLosers(1, 1) == []  # Single player
assert sol.circularGameLosers(2, 1) == []  # Both players visited
assert sol.circularGameLosers(2, 2) == [2]  # Only first player visited
assert sol.circularGameLosers(6, 1) == [2, 4, 6]  # Alternating visits
assert sol.circularGameLosers(10, 3) == [2, 3, 5, 6, 7, 8]  # Larger cycle
assert sol.circularGameLosers(5, 5) == [2, 3, 4, 5]  # Full wraparound each turn

Test	Why
`n=5, k=2`	Validates the main example
`n=4, k=4`	Tests immediate cycle repetition
`n=1, k=1`	Smallest possible input
`n=2, k=1`	Ensures all players can be visited
`n=2, k=2`	Tests wraparound to same player
`n=6, k=1`	Verifies repeated modular movement
`n=10, k=3`	Tests a larger nontrivial cycle
`n=5, k=5`	Ensures modulo arithmetic is correct

Edge Cases

One important edge case occurs when n = 1. In this scenario, there is only one friend in the circle. The ball starts with friend 1, and the very first pass immediately returns to the same player. Since that player already received the ball, the game ends instantly. There are no losers because the only friend participated. The implementation handles this naturally because the loop stops after the first repeated visit.

Another important case happens when k is exactly equal to n. In this situation, every movement of k steps results in no effective movement because (current + n) % n returns the same position. This means the starting player immediately receives the ball again. A faulty implementation might forget the modulo operation and produce out-of-range indices, but the modulo arithmetic correctly wraps around the circle.

A third edge case involves cycles that visit all players before repeating. For example, with certain combinations of n and k, every friend eventually receives the ball. In this case, the answer should be an empty list. The implementation correctly handles this because it only adds players whose visited value remains False.

Another subtle source of bugs is indexing. The problem statement uses 1-based numbering, while arrays in Python and Go are 0-based. Incorrect conversions can produce off-by-one errors in both movement calculations and result construction. The implementation avoids this by performing all computations using 0-based indices internally and converting back to 1-based numbering only when building the final answer.