Watch 10 video solutions for Find the Losers of the Circular Game, a easy level problem involving Array, Hash Table, Simulation. This walkthrough by Prakhar Agrawal has 775 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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. More formally, moving clockwise from the ith friend brings you to the (i+1)th friend for 1 <= i < n, and moving clockwise from the nth friend brings you to the 1st friend.
The rules of the game are as follows:
1st friend receives the ball.
1st friend passes it to the friend who is k steps away from them in the clockwise direction.2 * k steps away from them in the clockwise direction.3 * k steps away from them in the clockwise direction, and so on and so forth.In other words, on the ith turn, the friend holding the ball should pass it to the friend who is i * k steps away from them in the clockwise direction.
The game is finished when some friend receives the ball for the second time.
The losers of the game are friends who did not receive the ball in the entire game.
Given the number of friends, n, and an integer k, return the array answer, which contains the losers of the game in the ascending order.
Example 1:
Input: n = 5, k = 2 Output: [4,5] Explanation: The game goes as follows: 1) Start at 1st friend and pass the ball to the friend who is 2 steps away from them - 3rd friend. 2) 3rd friend passes the ball to the friend who is 4 steps away from them - 2nd friend. 3) 2nd friend passes the ball to the friend who is 6 steps away from them - 3rd friend. 4) The game ends as 3rd friend receives the ball for the second time.
Example 2:
Input: n = 4, k = 4 Output: [2,3,4] Explanation: The game goes as follows: 1) Start at the 1st friend and pass the ball to the friend who is 4 steps away from them - 1st friend. 2) The game ends as 1st friend receives the ball for the second time.
Constraints:
1 <= k <= n <= 50Problem Overview: You have n players standing in a circle. Starting from player 1, a ball is passed every round by increasing steps of k. Any player who never receives the ball during the process is considered a loser. Your task is to simulate the passing process and return all such players.
Approach 1: Simulation with Array or Set (O(n) time, O(n) space)
This approach directly simulates the game. Use a boolean array or set to track players who have already received the ball. Start from player 1 and repeatedly move i * k steps forward (modulo n) for round i. If a player receives the ball twice, the game stops. Every player marked as visited received the ball at least once. The remaining players are the losers. This approach mirrors the problem statement exactly and is easy to reason about. It works well when implementing straightforward simulation problems and uses constant operations per round.
Approach 2: Mathematical Iteration with Fewer Steps (O(n) time, O(n) space)
The passing pattern follows a predictable modular sequence. Each round moves the ball by i * k steps relative to the previous position. Instead of maintaining full simulation logic, you repeatedly compute the next position using modular arithmetic: current = (current + step * k) % n. Continue until a previously visited index appears. Store visited players in an array or hash table style structure. This avoids unnecessary checks and keeps the implementation compact while still running in linear time.
The key insight is that each player can receive the ball at most once before the sequence repeats. Because of this, the process performs at most n iterations. The final step is scanning the visited array and collecting players that never appeared.
Recommended for interviews: The simulation approach is what interviewers usually expect first. It shows you can translate the rules of the problem directly into code using arrays and modular arithmetic. After that, recognizing the mathematical pattern in the circular movement demonstrates stronger reasoning about array indexing and cyclic behavior.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulation with Array or Set | O(n) | O(n) | Best when implementing the game rules directly and explaining logic clearly in interviews |
| Mathematical Iteration with Modular Arithmetic | O(n) | O(n) | When you recognize the cyclic pattern and want a cleaner implementation with fewer checks |