algoadvance

Leetcode 2682. Find the Losers of the Circular Game

Problem Statement

You are given a circular game with n players and a value k. The players are sequentially numbered from 1 to n, standing in a circle. Starting with player 1, every k-th player gets removed from the circle. After removing a player, the next player immediately to the removed player’s right continues the game. The process repeats until only one player remains.

You need to return a list of all players that lose the game in the order they were removed.

Example:

Input: n = 5, k = 2
Output: [2, 4, 1, 5]

Constraints:

• 1 <= n <= 100
• 1 <= k <= 100

Clarifying Questions

1. Will the list of losers always be in the order they were removed?
   • Yes, the list should be in the exact order in which players are removed.
2. Is the number of players n and the step count k always positive integers?
   • Yes, both n and k are positive integers as given by the constraints.
3. Should the function handle edge cases where n or k is 1?
   • Yes, for n = 1, the list of losers would be empty since no one will be removed.

Strategy

1. Use a list to represent the players.
2. Iterate through the list, removing every k-th player.
3. Use modulo arithmetic to handle the circular nature of the list.
4. Keep track of the order of removal in a separate list.
5. Continue the process until only one player remains.
6. Return the list of removed players.

Code

import java.util.ArrayList;
import java.util.List;

public class CircularGameLosers {
    public List<Integer> findLosers(int n, int k) {
        List<Integer> players = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            players.add(i);
        }
        
        List<Integer> losers = new ArrayList<>();
        int index = 0;
        
        while (players.size() > 1) {
            index = (index + k - 1) % players.size();
            losers.add(players.remove(index));
        }
        
        return losers;
    }

    public static void main(String[] args) {
        CircularGameLosers game = new CircularGameLosers();
        System.out.println(game.findLosers(5, 2)); // Output: [2, 4, 1, 5]
    }
}

Time Complexity

• Initialization of player list: O(n)
• Removing each player: O(n) because we might have to remove up to n-1 players, each removal operation on an ArrayList (removing by index) takes O(n) time.
• Overall Time Complexity: O(n^2). This is because for each removal operation, the array might have to shift elements.

Explanation

1. We start by creating a list of players numbered from 1 to n.
2. The variable index is used to keep track of the current position in the list.
3. In each iteration, calculate the next index to remove using (index + k - 1) % players.size(). This takes care of the circular nature.
4. Remove the player at this index and add them to the losers list.
5. Continue until only one player remains in the players list.
6. Return the list of losers.

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?