Find the Winner of the Circular Game

Problem Description

There are n friends playing a game in a circle. Starting from the first friend, they count k friends clockwise, and the friend who is counted last leaves the circle. This process continues until only one friend remains, who is declared the winner. Given the number of friends, n, and the count k, return the winner of the game.

Key Insights

• The problem can be approached using a simulation of counting and removing friends from the circle.
• As friends are eliminated, the circle shrinks, which requires careful handling of indices.
• The counting wraps around the circle, which can be managed using modulo arithmetic.
• The solution can be optimized to run in linear time with constant space.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The game can be simulated using a circular linked list approach or by maintaining an array to represent the friends. Each time a friend is eliminated, the counting continues from the next friend, adjusting the index accordingly using modulo operations to handle the circular nature.

The key steps are:

1. Initialize an array to represent the friends.
2. Start counting from the first friend.
3. Use modulo arithmetic to determine the next friend to be counted and removed.
4. Repeat until only one friend remains.

Code Solutions