#2682

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find the Losers of the Circular Game

Simulate a ball-passing game around a circle using array scanning and hash lookup to find friends who never receive the ball.

array hash table simulation

Problem Statement

n friends are sitting in a circle, numbered 1 to n clockwise. The first friend starts with a ball and passes it to another friend k steps away, wrapping around the circle as needed.

The game continues with each friend who receives the ball passing it k steps ahead. The game ends when a friend receives the ball for the second time. Your task is to return a list of friends who never received the ball.

Examples

Example 1

Input: n = 5, k = 2

Output: [4,5]

The game goes as follows:

Start at 1st friend and pass the ball to the friend who is 2 steps away from them - 3rd friend.
3rd friend passes the ball to the friend who is 4 steps away from them - 2nd friend.
2nd friend passes the ball to the friend who is 6 steps away from them - 3rd friend.
The game ends as 3rd friend receives the ball for the second time.

Example 2

Input: n = 4, k = 4

Output: [2,3,4]

The game goes as follows:

Start at the 1st friend and pass the ball to the friend who is 4 steps away from them - 1st friend.
The game ends as 1st friend receives the ball for the second time.

Constraints

1 <= k <= n <= 50

Solution Approach

Simulate ball passing

Use a set to track friends who have received the ball. Start from friend 1 and repeatedly move k steps clockwise, adding each new friend to the set until a repeat occurs.

Scan for losers

After the simulation ends, scan through 1 to n and collect friends not in the received-ball set. This ensures accurate identification of losers.

Optimize with modulo

Calculate the next friend using modulo arithmetic to wrap around the circle, avoiding index errors and making array scanning efficient.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each friend is visited at most once during simulation. Space complexity is O(n) due to the set storing which friends received the ball.

What Interviewers Usually Probe

Emphasize simulation over mathematical shortcuts.
Check that modulo arithmetic correctly wraps around the circle.
Ensure the set correctly detects repeated ball receipt.

Common Pitfalls or Variants

Common pitfalls

Forgetting to wrap around using modulo can cause index errors.
Adding a friend to the losers list who actually received the ball.
Incorrectly stopping the simulation before a friend receives the ball twice.

Follow-up variants

Change k dynamically on each pass to increase simulation complexity.
Return the order in which losers would have received the ball if the game continued.
Simulate the game with multiple balls passed simultaneously.

FAQ

What is the key pattern in Find the Losers of the Circular Game?

The main pattern is array scanning combined with hash lookup to track who has received the ball.

Can I use a mathematical formula instead of simulation?

While possible in some games, this problem requires explicit simulation to correctly identify all losers.

How do I handle wrapping around the circle?

Use modulo arithmetic: next_friend = (current_friend + k - 1) % n + 1 to stay within 1 to n.

What data structure ensures fast lookup for received friends?

A hash set allows O(1) lookup to check if a friend has already received the ball.

Is the order of losers important in the output?

Yes, scan friends from 1 to n after simulation to maintain ascending order in the result.

terminal

Solution

Solution 1: Simulation

We use an array `vis` to record whether each friend has received the ball, initially, all friends have not received the ball. Then, we simulate the game process according to the rules described in the problem statement until a friend receives the ball for the second time.

1

2

3

4

5

6

7

8

9

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]]

Continue Practicing

#2744 find maximum number of string pairs #2766 relocate marbles #2593 find score of an array after marking all elements