algoadvance

Leetcode 2682. Find the Losers of the Circular Game

Problem Statement

In this task, you are given a circular game with n participants numbered from 1 to n. Initially, the game starts with the first player, and you have to determine who will be the losers.

You need to write a function that determines the list of players who will be out of the game based on the given rules. The function should return these losers in ascending order.

The rules are:

• Players are erased from the circle after each complete pass (starting from player 1) until only one player remains.
• Once a player is erased, they are out of the circle and do not participate in further passes.

Clarifying Questions

1. Clarification on Circular Nature: Can participants be removed directly, and the circle updated dynamically?
2. Output Format: Should the output include the remaining single winner or just the eliminated players?
3. Bounds: What are the constraints on n?

Assumptions based on standard circular elimination games:

• Typically, the game continues until only one player remains.
• We’ll provide the list of all eliminated players excluding the last remaining player.

Strategy

1. Use a circular linked list simulation to track active participants.
2. Iteratively remove players following the elimination rule until one remains.
3. Collect and return the eliminated players in their order of elimination.

Code

Here is a possible implementation in C++:

#include <iostream>
#include <vector>

std::vector<int> findLosers(int n) {
    std::vector<int> losers;
    std::vector<int> players(n);
    
    // Initialize players
    for (int i = 0; i < n; ++i) {
        players[i] = i + 1;
    }
    
    int currentIndex = 0; // starts from the first player (index 0)
    
    while (players.size() > 1) {
        // computes the index of the player to be removed
        currentIndex = (currentIndex + 1) % players.size();
        losers.push_back(players[currentIndex]);
        
        // remove the player from the game
        players.erase(players.begin() + currentIndex);
        
        // correct the currentIndex as currentIndex has shifted
        if (currentIndex == players.size()) {
            currentIndex = 0;
        }
    }
    
    return losers;
}

int main() {
    int n = 5;
    std::vector<int> losers = findLosers(n);
    
    std::cout << "The losers in ascending order are: ";
    for (int loser : losers) {
        std::cout << loser << " ";
    }
    std::cout << std::endl;

    return 0;
}

Strategy Explained

1. Initialization:
   • Create a vector players to store the current players in the game and initialize it with player numbers from 1 to n.
2. Circular Elimination:
   • Use a currentIndex to track the current position.
   • Continuously calculate and remove the next player (using modular arithmetic to wrap around).
   • After removal, adjust the currentIndex to point correctly to the next player in a circular fashion.
3. Collect Losers:
   • Every time a player is removed, record it in the losers vector.
   • The loop continues until only one player remains.

Time Complexity

• Initialization Complexity: O(n) - Initializing the players’ vector.
• Elimination Loop Complexity: O(n^2) - Each elimination involves a shift operation in a vector, leading to an O(n) complexity for each of the n-1 removals due to the vector’s erase operation.

Therefore, the overall time complexity is O(n^2). This can be further optimized using a different data structure for efficient removal, but for standard implementations, this approach is simple and intuitive.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?