Find the Losers of the Circular Game solution and explanation
9 more videos on this problem
Leetcode Weekly contest 345 - Easy - Find the Losers of the Circular GamePrakhar Agrawal · 5:19 · 776 views
Leetcode 2682. Find the Losers of the Circular Game | Weekly Contest 345 | Leetcode weekly contestOffCampus Phodenge | Aman Chowdhury · 11:43 · 511 views
6430. Find the Losers of the Circular Game | Leetcode Weekly Contest 345 | Solution Code.Optimization · 2:07 · 401 views
Find the Losers of the Circular Game - Leetcode 2682Algorithms Casts · 10:30 · 384 views
Leetcode weekly Contest 345 solution l Hindi | Find the Losers of the Circular GamePawan Kumar Giri · 18:10 · 296 views
2682. Find the Losers of the Circular Game (Leetcode Easy)Programming Live with Larry · 5:14 · 263 views
2682. Find the Losers of the Circular Game - leetcodeFateen Academy - أكاديمية فطين · 29:07 · 191 views
Find the Losers of the Circular Game LeetCode Contest #leetcodeSusheel Sahu(Aspirant) · 0:34 · 130 views
Find the Losers of the Circular Game #LeetCode #jav #dsa #recursion #FindtheLosersoftheCircularGameCodeVia · 4:35 · 94 views
leetcode 2682. Find the Losers of the Circular Game - mod operation and info retrieval using dictCode-Yao · 9:39 · 41 views
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. 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,
1stfriend passes it to the friend who isksteps away from them in the clockwise direction. - After that, the friend who receives the ball should pass it to the friend who is
2 * ksteps away from them in the clockwise direction. - After that, the friend who receives the ball should pass it to the friend who is
3 * ksteps 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
Approach overview
Problem 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 1: Simulation with Array or Set
This approach involves simulating the game by recording which friends have received the ball. Start with friend 1 and pass the ball in increments of i * k where i is the turn number, being careful to use modulo n to wrap around the circle of friends. Use an array or set to keep track of which friends have received the ball. The game ends when a friend receives the ball for a second time, and the friends who never received the ball are the losers.
def find_losers(n, k):
received = [False] * (n + 1)
current = 1
step = 1
received[current] = True
while True:
current = (current + step * k - 1) % n + 1
if received[current]:
break
received[current] = True
step += 1
losers = [i for i in range(1, n + 1) if not received[i]]
return losers
losers = find_losers(5, 2)
print(losers)import java.util.ArrayList;
import java.util.List;
public class CircularGame {
public static List<Integer> findLosers(int n, int k) {
boolean[] received = new boolean[n + 1];
int current = 1;
int step = 1;
received[current] = true;
while (true) {
current = (current + step * k - 1) % n + 1;
if (received[current]) break;
received[current] = true;
step++;
}
List<Integer> losers = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (!received[i]) {
losers.add(i);
}
}
return losers;
}
public static void main(String[] args) {
int n = 5, k = 2;
List<Integer> losers = findLosers(n, k);
for (int x : losers) {
System.out.print(x + " ");
}
}
}#include <iostream>
#include <vector>
using namespace std;
vector<int> findLosers(int n, int k) {
vector<bool> received(n + 1, false);
int current = 1;
int step = 1;
received[current] = true;
while (true) {
current = (current + step * k - 1) % n + 1;
if (received[current]) break;
received[current] = true;
step++;
}
vector<int> losers;
for (int i = 1; i <= n; i++) {
if (!received[i]) {
losers.push_back(i);
}
}
return losers;
}
int main() {
int n = 5, k = 2;
vector<int> losers = findLosers(n, k);
for (int x : losers) {
cout << x << " ";
}
return 0;
}function findLosers(n, k) {
let received = Array(n + 1).fill(false);
let current = 1;
let step = 1;
received[current] = true;
while (true) {
current = (current + step * k - 1) % n + 1;
if (received[current]) break;
received[current] = true;
step++;
}
let losers = [];
for (let i = 1; i <= n; i++) {
if (!received[i]) {
losers.push(i);
}
}
return losers;
}
console.log(findLosers(5, 2));#include <stdio.h>
#include <stdbool.h>
void findLosers(int n, int k, int *out, int *outSize) {
bool received[51] = {false};
int current = 1;
int step = 1;
received[current] = true;
while (true) {
current = (current + step * k - 1) % n + 1;
if (received[current]) break;
received[current] = true;
step++;
}
int index = 0;
for (int i = 1; i <= n; i++) {
if (!received[i]) {
out[index++] = i;
}
}
*outSize = index;
}
int main() {
int n = 5, k = 2;
int losers[50];
int size = 0;
findLosers(n, k, losers, &size);
for (int i = 0; i < size; i++) {
printf("%d ", losers[i]);
}
return 0;
}using System;
using System.Collections.Generic;
class CircularGame {
public static List<int> FindLosers(int n, int k) {
bool[] received = new bool[n + 1];
int current = 1;
int step = 1;
received[current] = true;
while (true) {
current = (current + step * k - 1) % n + 1;
if (received[current]) break;
received[current] = true;
step++;
}
List<int> losers = new List<int>();
for (int i = 1; i <= n; i++) {
if (!received[i]) {
losers.Add(i);
}
}
return losers;
}
static void Main() {
int n = 5, k = 2;
List<int> losers = FindLosers(n, k);
foreach (int x in losers) {
Console.Write(x + " ");
}
}
}Python solution that follows the same simulation logic. It uses a list to record received status and a list comprehension to filter out those who never got the ball.
Time Complexity: O(n). Space Complexity: O(n) for the tracking list.
Approach 2: Mathematical Approach with Fewer Iterations
This approach optimizes the iteration by using mathematical insights into how friends are passed the ball. By keeping track of indexes and avoiding full simulation where possible, we can reduce unnecessary passes. The focus is on identifying repeat earlier, minimizing the steps taken.
def find_losers(n, k):
received = [False] * (n + 1)
received[1] = True
current = 1
for step in range(1, n + 1):
current = (current + step * k - 1) % n + 1
if received[current]:
break
received[current] = True
losers = [i for i in range(1, n + 1) if not received[i]]
return losers
losers = find_losers(5, 2)
print(losers)import java.util.ArrayList;
import java.util.List;
public class CircularGame {
public static List<Integer> findLosers(int n, int k) {
boolean[] received = new boolean[n + 1];
received[1] = true;
int current = 1;
for (int step = 1;; step++) {
current = (current + step * k - 1) % n + 1;
if (received[current]) break;
received[current] = true;
}
List<Integer> losers = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (!received[i]) {
losers.add(i);
}
}
return losers;
}
public static void main(String[] args) {
int n = 5, k = 2;
List<Integer> losers = findLosers(n, k);
for (int x : losers) {
System.out.print(x + " ");
}
}
}#include <iostream>
#include <vector>
using namespace std;
vector<int> findLosers(int n, int k) {
vector<bool> received(n + 1, false);
received[1] = true;
int current = 1;
for (int step = 1;; step++) {
current = (current + step * k - 1) % n + 1;
if (received[current]) break;
received[current] = true;
}
vector<int> losers;
for (int i = 1; i <= n; i++) {
if (!received[i]) {
losers.push_back(i);
}
}
return losers;
}
int main() {
int n = 5, k = 2;
vector<int> losers = findLosers(n, k);
for (int x : losers) {
cout << x << " ";
}
return 0;
}function findLosers(n, k) {
let received = Array(n + 1).fill(false);
let current = 1;
received[1] = true;
for (let step = 1;; step++) {
current = (current + step * k - 1) % n + 1;
if (received[current]) break;
received[current] = true;
}
let losers = [];
for (let i = 1; i <= n; i++) {
if (!received[i]) {
losers.push(i);
}
}
return losers;
}
console.log(findLosers(5, 2));#include <stdio.h>
#include <stdbool.h>
void findLosers(int n, int k, int *out, int *outSize) {
bool received[51] = {false};
received[1] = true;
int current = 1;
for (int step = 1;; step++) {
current = (current + step * k - 1) % n + 1;
if (received[current]) break;
received[current] = true;
}
int index = 0;
for (int i = 1; i <= n; i++) {
if (!received[i]) {
out[index++] = i;
}
}
*outSize = index;
}
int main() {
int n = 5, k = 2;
int losers[50];
int size = 0;
findLosers(n, k, losers, &size);
for (int i = 0; i < size; i++) {
printf("%d ", losers[i]);
}
return 0;
}using System;
using System.Collections.Generic;
class CircularGame {
public static List<int> FindLosers(int n, int k) {
bool[] received = new bool[n + 1];
received[1] = true;
int current = 1;
for (int step = 1;; step++) {
current = (current + step * k - 1) % n + 1;
if (received[current]) break;
received[current] = true;
}
List<int> losers = new List<int>();
for (int i = 1; i <= n; i++) {
if (!received[i]) {
losers.Add(i);
}
}
return losers;
}
static void Main() {
int n = 5, k = 2;
List<int> losers = FindLosers(n, k);
foreach (int x in losers) {
Console.Write(x + " ");
}
}
}With Python, the optimized solution calculates the passing steps directly within a single loop, improving efficiency in determining who received the ball.
Time Complexity: O(n). Space Complexity: O(n).
Approach 3: 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.
In the simulation process, we use two variables i and p to represent the current friend holding the ball and the current passing step length, respectively. Initially, i=0, p=1, indicating the first friend receives the ball. Each time the ball is passed, we update i to (i+p times k) bmod n, representing the next friend's number to receive the ball, and then update p to p+1, representing the step length for the next pass. The game ends when a friend receives the ball for the second time.
Finally, we iterate through the array vis and add the numbers of friends who have not received the ball to the answer array.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of friends.
function circularGameLosers(n: number, k: number): number[] {
const vis = new Array(n).fill(false);
const ans: number[] = [];
for (let i = 0, p = 1; !vis[i]; p++) {
vis[i] = true;
i = (i + p * k) % n;
}
for (let i = 0; i < vis.length; i++) {
if (!vis[i]) {
ans.push(i + 1);
}
}
return ans;
}func circularGameLosers(n int, k int) (ans []int) {
vis := make([]bool, n)
for i, p := 0, 1; !vis[i]; p++ {
vis[i] = true
i = (i + p*k) % n
}
for i, x := range vis {
if !x {
ans = append(ans, i+1)
}
}
return
}impl Solution {
pub fn circular_game_losers(n: i32, k: i32) -> Vec<i32> {
let mut vis: Vec<bool> = vec![false; n as usize];
let mut i = 0;
let mut p = 1;
while !vis[i] {
vis[i] = true;
i = (i + p * (k as usize)) % (n as usize);
p += 1;
}
let mut ans = Vec::new();
for i in 0..vis.len() {
if !vis[i] {
ans.push((i + 1) as i32);
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Simulation with Array or Set | Time Complexity: O(n). Space Complexity: O(n) for the tracking list. |
| Mathematical Approach with Fewer Iterations | Time Complexity: O(n). Space Complexity: O(n). |
| Simulation | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Find the Losers of the Circular Game easy or hard?
Find the Losers of the Circular Game is classified as an Easy problem on LeetCode. The challenge mainly involves careful simulation and correct use of modulo arithmetic for circular movement rather than complex algorithms.
How to solve Find the Losers of the Circular Game in O(n)?
Use simulation with modular arithmetic. Maintain a visited array of size n and start from index 0. For round i, move (i * k) steps ahead using (current + i * k) % n. Stop when you land on a previously visited player. Finally, return all players whose visited value is false.
Find the Losers of the Circular Game Python or Java solution
In both Python and Java, the solution uses a visited array and modular arithmetic to simulate ball passing. Track the current player, increment the step multiplier each round, and stop when a player repeats. Finally, iterate through the visited array to collect the players who never received the ball.
What is the best approach for Find the Losers of the Circular Game?
The most practical approach is simulation using a boolean array or set to track visited players. Start from player 1 and repeatedly move i * k steps forward using modulo arithmetic. Stop when a player receives the ball twice. The unvisited players are the losers. This runs in O(n) time and O(n) space.
Is Find the Losers of the Circular Game asked at Google/Amazon/Meta?
This problem represents a typical array simulation and modular arithmetic question commonly seen in coding interviews. Variants of circular traversal and step-based movement appear in interviews at companies like Amazon, Google, and Microsoft when testing problem modeling and simulation skills.
What data structure is used in Find the Losers of the Circular Game?
The main data structure is an array or hash set used to track which players have received the ball. Arrays are usually preferred because player indices are sequential from 1 to n, allowing constant-time updates and checks during the simulation.
What is the time complexity of Find the Losers of the Circular Game?
The standard solution runs in O(n) time because each player can receive the ball at most once before the sequence repeats. A visited array tracks players who have already received the ball. The final pass to collect losers also takes O(n) time, resulting in linear complexity overall.