Leetcode 2682: Find the Losers of the Circular Game
In this game, there are
n friends sitting in a circle, numbered from 1 to n. The game starts with the 1st friend receiving a ball. The ball is passed to a friend k steps away in a clockwise direction, and then on each subsequent turn, the ball is passed to the friend i * k steps away, where i is the turn number (starting from 1). The game ends when any friend receives the ball for the second time. The friends who never receive the ball are considered the losers. The task is to return the list of losers in ascending order.Problem
Approach
Steps
Complexity
Input: You are given two integers, `n` and `k`, where `n` is the number of friends and `k` is the number of steps the ball is passed on each turn.
Example: Input: n = 6, k = 3
Constraints:
• 1 <= k <= n <= 50
Output: Return an array containing the losers of the game (the friends who never received the ball), sorted in ascending order.
Example: Output: [2, 4, 5, 6]
Constraints:
• The output should be an array of integers.
Goal: The goal is to simulate the passing of the ball based on the given rules and track which friends never receive the ball.
Steps:
• Step 1: Initialize an array to track whether each friend has received the ball.
• Step 2: Start with the 1st friend receiving the ball and pass it `k` steps away on each turn.
• Step 3: After each pass, mark the friend as having received the ball and continue passing it in increasing multiples of `k`.
• Step 4: Stop the game when any friend receives the ball for the second time.
• Step 5: Gather all the friends who never received the ball and return them as the losers.
Goal: The solution must handle cases efficiently even with the maximum values for `n` and `k`.
Steps:
• The ball passing process is repeated until a friend receives the ball a second time.
Assumptions:
• All input values are valid as per the problem constraints.
• The game will always end when a friend receives the ball for the second time.
• Input: Input: n = 6, k = 3
• Explanation: In this case, the ball starts with the 1st friend and is passed 3 steps away each time. The game proceeds as follows: 1st friend -> 4th friend -> 1st friend (game ends). The losers are the friends who never received the ball: 2nd, 5th, and 6th friends.
• Input: Input: n = 4, k = 2
• Explanation: The ball starts with the 1st friend and is passed 2 steps away each time. The game proceeds as follows: 1st friend -> 3rd friend -> 1st friend (game ends). The losers are the 2nd and 4th friends.
Approach: We will simulate the game by passing the ball as per the rules and track the friends who receive the ball, using a simple array to mark each friend as they receive the ball.
Observations:
• We need to simulate the ball passing efficiently to track the friends who received the ball.
• A straightforward simulation should suffice as `n` is small enough (up to 50).
Steps:
• Step 1: Initialize an array `rcvd` of size `n` to track whether each friend has received the ball.
• Step 2: Start with the 1st friend and pass the ball by moving `k`, `2k`, `3k` steps, and so on.
• Step 3: Mark each friend who receives the ball. Stop when a friend gets the ball for the second time.
• Step 4: Collect the friends who have not received the ball and return them as the losers.
Empty Inputs:
• There will always be at least one friend, so no empty inputs.
Large Inputs:
• The solution should be efficient enough for `n` up to 50.
Special Values:
• The case where `k` equals `n` should be handled correctly, as the ball will be passed back to the 1st friend immediately.
Constraints:
• The ball will always return to a friend who has already received it, ensuring the game ends.
vector<int> circularGameLosers(int n, int k) {
vector<int> rcvd(n, 0);
int i = 0;
int cnt = 1;
rcvd[0] = 1;
while(rcvd[i] == 1) {
i = (i + cnt * k) % n;
if(rcvd[i] == 1) break;
rcvd[i] = 1;
cnt++;
}
vector<int> ans;
for(int j = 0; j < n; j++) {
// cout << rcvd[j] << " ";
if(rcvd[j] == 0) ans.push_back(j + 1);
}
return ans;
}
1 : Function Definition
vector<int> circularGameLosers(int n, int k) {
The function 'circularGameLosers' is defined to take two arguments: an integer 'n' representing the number of players and an integer 'k' representing the number of steps between eliminations. The goal is to return the list of players who are not eliminated.
2 : Variable Initialization
vector<int> rcvd(n, 0);
A vector 'rcvd' is initialized to size 'n', with all values set to 0, representing that no players are initially eliminated.
3 : Variable Initialization
int i = 0;
The variable 'i' is initialized to 0 and will be used to keep track of the current player in the game.
4 : Variable Initialization
int cnt = 1;
The variable 'cnt' is initialized to 1 and will keep track of the number of steps taken between eliminations.
5 : First Elimination
rcvd[0] = 1;
The first player (index 0) is marked as eliminated by setting 'rcvd[0]' to 1.
6 : Game Loop
while(rcvd[i] == 1) {
A while loop is initiated, continuing as long as the current player 'i' is marked as eliminated.
7 : Player Elimination Calculation
i = (i + cnt * k) % n;
The index 'i' is updated by moving 'k' steps forward, multiplied by 'cnt', and taken modulo 'n' to ensure it stays within the circular bounds of the array.
8 : Elimination Check
if(rcvd[i] == 1) break;
If the current player is already eliminated, the loop breaks, ending the game.
9 : Player Elimination
rcvd[i] = 1;
The current player 'i' is marked as eliminated by setting 'rcvd[i]' to 1.
10 : Step Increment
cnt++;
The 'cnt' variable is incremented to account for the next step in the game, which will be used to calculate the next elimination.
11 : Result Vector Initialization
vector<int> ans;
An empty vector 'ans' is initialized to store the indices of players who were not eliminated.
12 : Losers Collection Loop
for(int j = 0; j < n; j++) {
A loop iterates through the 'rcvd' vector to identify the players who were not eliminated.
13 : Losers Identification
if(rcvd[j] == 0) ans.push_back(j + 1);
If the player 'j' is not eliminated (i.e., 'rcvd[j] == 0'), their index (adjusted by 1) is added to the 'ans' vector.
14 : Return Result
return ans;
The 'ans' vector, containing the indices of the players who were not eliminated, is returned as the final result.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: We iterate over the friends once to simulate the ball passing process, which takes linear time.
Best Case: O(n)
Worst Case: O(n)
Description: We use an array of size `n` to track the friends who received the ball.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus