# Find the Losers of the Circular Game
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-losers-of-the-circular-game)
Canonical: https://scaleengineer.com/dsa/problems/find-the-losers-of-the-circular-game
**Data structures:** Array, Hash Table
---
## 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**. 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.
* After that, `1st` friend passes it to the friend who is `k` steps away from them in the **clockwise** direction.
* After that, the friend who receives the ball should pass it to the friend who is `2 * k` steps away from them in the **clockwise** direction.
* After that, the friend who receives the ball should pass it to the friend who is `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 <= 50`
# Approaches
## Brute-Force Simulation with a List
This approach directly simulates the game turn by turn. We use a list to keep track of all the friends who have received the ball. The game proceeds until a friend who is already in our list is about to receive the ball again.
**Time:** O(n^2). The simulation loop runs at most `n` times. Inside the loop, `received.contains()` takes O(i) time where `i` is the current turn number. This leads to a sum of `1 + 2 + ... + n`, which is O(n^2). The final step of finding losers also takes O(n^2) because for each of the `n` friends, we perform a linear search on the `received` list (which can have up to `n` elements). · **Space:** O(n). We use a list `received` to store the winners and a list `losersList` for the losers. Both can grow up to size `n`.
**Pros:** Simple to understand and implement.; Directly follows the logic of the problem statement.
**Cons:** Inefficient due to the repeated linear searches on the `received` list.; Will be slow for larger values of `n` (though `n` is small here).
### Explanation
We start with friend 1 having the ball. We maintain a list, say `received`, to store the IDs of friends who have held the ball. Initially, this list contains just `1`.
We simulate the game in a loop. In each turn `i` (starting from `i=1`), the current friend passes the ball to another friend who is `i * k` steps away in the clockwise direction.
The position of the next friend is calculated using the formula `(current_position - 1 + pass_distance) % n + 1`.
Before passing the ball, we check if the intended recipient is already in our `received` list.
- If they are, the game ends. We break the loop.
- If they are not, we add them to the `received` list, update the current player, and proceed to the next turn.
After the simulation ends, we iterate through all friends from 1 to `n`. For each friend, we check if their ID is present in the `received` list. If not, we add them to our `losers` list.
Finally, we convert the `losers` list to an array and return it. The list will be naturally sorted as we check friends in ascending order.
Here is the Java implementation for this approach:
```java
import java.util.ArrayList;
import java.util.List;
class Solution {
public int[] findLosers(int n, int k) {
List received = new ArrayList<>();
int currentFriend = 1;
int turn = 1;
received.add(currentFriend);
while (true) {
int distance = turn * k;
int nextFriend = (currentFriend - 1 + distance) % n + 1;
if (received.contains(nextFriend)) {
break;
}
received.add(nextFriend);
currentFriend = nextFriend;
turn++;
}
List losersList = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (!received.contains(i)) {
losersList.add(i);
}
}
int[] losersArray = new int[losersList.size()];
for (int i = 0; i < losersList.size(); i++) {
losersArray[i] = losersList.get(i);
}
return losersArray;
}
}
```
### Algorithm
- Initialize an empty list `received` to store the IDs of friends who have received the ball.
- Initialize `currentFriend = 1`, `turn = 1`.
- Add `currentFriend` to the `received` list.
- Start a loop that continues indefinitely:
- Calculate the pass distance: `distance = turn * k`.
- Calculate the next friend's ID: `nextFriend = (currentFriend - 1 + distance) % n + 1`.
- Check if `nextFriend` is already in the `received` list. This requires a linear scan of the list.
- If `nextFriend` is in the list, break the loop.
- Otherwise, add `nextFriend` to the `received` list, update `currentFriend = nextFriend`, and increment `turn`.
- Initialize an empty list `losers`.
- Iterate from `i = 1` to `n`:
- Check if `i` is in the `received` list.
- If `i` is not in the list, add it to `losers`.
- Convert the `losers` list to an array and return it.
## Optimized Simulation with a Boolean Array
This approach improves upon the brute-force simulation by using a more efficient data structure to track which friends have received the ball. Instead of a list, we use a boolean array (or a hash set) for O(1) lookups. This significantly speeds up the process of checking if a friend has already received the ball.
**Time:** O(n). The simulation loop can run at most `n` times because there are `n` friends, and the game stops when a friend receives the ball for the second time. Each operation inside the loop is O(1). After the loop, we iterate `n` times to find the losers. Thus, the total time complexity is O(n) + O(n) = O(n). · **Space:** O(n). We use a boolean array `hasReceived` of size `n+1` and a list to store the losers, which can also be of size up to `n-1`.
**Pros:** Highly efficient with linear time complexity.; Optimal for the given constraints.; Simple implementation using a boolean array for fast lookups.
**Cons:** Uses extra space proportional to `n`, which is unavoidable for this problem.
### Explanation
We use a boolean array, `hasReceived`, of size `n+1` (using 1-based indexing for convenience), initialized to `false`. This array will act as a direct-access table to check if a friend has received the ball.
The simulation starts with friend 1. We mark `hasReceived[1] = true`.
We then enter a loop to simulate the game turns. In each turn `i`, we calculate the next friend to receive the ball using the formula: `(current_friend - 1 + i * k) % n + 1`.
Before passing the ball, we check `hasReceived[nextFriend]`. Since this is an array lookup, it takes constant time, O(1).
- If `hasReceived[nextFriend]` is `true`, it means this friend has received the ball before, so the game ends. We break the loop.
- If it's `false`, we mark `hasReceived[nextFriend] = true`, update the current player, and continue to the next turn.
Once the simulation is complete, we create a list for the losers. We iterate from friend 1 to `n`. If `hasReceived[i]` is `false`, we add `i` to our list of losers.
Finally, we convert the list of losers to an array and return it. The list is already sorted because we iterate in ascending order.
Here is the Java implementation for this approach:
```java
import java.util.ArrayList;
import java.util.List;
class Solution {
public int[] findLosers(int n, int k) {
boolean[] hasReceived = new boolean[n + 1];
int currentFriend = 1;
int turn = 1;
hasReceived[currentFriend] = true;
while (true) {
int distance = turn * k;
int nextFriend = (currentFriend - 1 + distance) % n + 1;
if (hasReceived[nextFriend]) {
break;
}
hasReceived[nextFriend] = true;
currentFriend = nextFriend;
turn++;
}
List losersList = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (!hasReceived[i]) {
losersList.add(i);
}
}
int[] losersArray = new int[losersList.size()];
for (int i = 0; i < losersList.size(); i++) {
losersArray[i] = losersList.get(i);
}
return losersArray;
}
}
```
### Algorithm
- Initialize a boolean array `hasReceived` of size `n + 1` to all `false`.
- Initialize `currentFriend = 1`, `turn = 1`.
- Mark the starting friend: `hasReceived[currentFriend] = true`.
- Start a loop that continues indefinitely:
- Calculate the pass distance: `distance = turn * k`.
- Calculate the next friend's ID: `nextFriend = (currentFriend - 1 + distance) % n + 1`.
- Check if `hasReceived[nextFriend]` is `true`.
- If it is, break the loop.
- Otherwise, set `hasReceived[nextFriend] = true`, update `currentFriend = nextFriend`, and increment `turn`.
- Initialize an empty list `losers`.
- Iterate from `i = 1` to `n`:
- If `hasReceived[i]` is `false`, add `i` to the `losers` list.
- Convert the `losers` list to an array and return it.
# Solutions
### Java
```java
class Solution {
public
int[] circularGameLosers(int n, int k) {
boolean[] vis = new boolean[n];
int cnt = 0;
for (int i = 0, p = 1; !vis[i]; ++p) {
vis[i] = true;
++cnt;
i = (i + p * k) % n;
}
int[] ans = new int[n - cnt];
for (int i = 0, j = 0; i < n; ++i) {
if (!vis[i]) {
ans[j++] = i + 1;
}
}
return ans;
}
}
```
### CPP
```cpp
class Solution {
public:
vector circularGameLosers(int n, int k) {
bool vis[n];
memset(vis, false, sizeof(vis));
for (int i = 0, p = 1; !vis[i]; ++p) {
vis[i] = true;
i = (i + p * k) % n;
}
vector ans;
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
ans.push_back(i + 1);
}
}
return ans;
}
};
```
### Python
```python
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]]
```