Search⌘ K
AI Features

Problem: Find the Winner of the Circular Game

Explore how to determine the winner in a circular elimination game by using a queue data structure in Python. Learn to simulate the process of removing players step-by-step, understand queue rotations, and analyze the time and space complexity of this approach. This lesson helps build practical skills in applying queues to solve real-world problems efficiently.

Statement

A group of n friends is seated in a circle, numbered from 11 to n in clockwise order. Specifically, moving clockwise from friend i leads to friend i + 1 for 11 \leq i << n, and moving clockwise from friend n wraps back to friend 11.

The game proceeds as follows:

  1. Begin at friend 11.

  2. Starting from the current friend, count k friends in the clockwise direction (including the current friend). The counting wraps around the circle and may count some friends more than once.

  3. The last friend counted is eliminated ...