Find The Winner Of The Circular Game - Leetcode Solution

Problem:

There are n children standing in a circle, numbered from 0 to n - 1. Starting from the first child, you will play the following game:

Count the next k children in the clockwise direction, including the child that you are currently on. The child that you land on is now out of the game. Keep counting the next k children in the clockwise direction, skipping over the children that were eliminated in the previous rounds, until only one child remains in the circle.

Return the index of the last child that remains in the circle.

Solution:

The problem of finding the winner of the circular game can be solved using recursion. We can implement this using a recursive function that takes in the number of children in the circle and the starting position. We can recursively remove kth element until only one element is left in the circle. Let us call this function the "circleGame":

The steps to implement the recursive function are as follows:

First, we check if there is only one child left in the circle. If there is, then we return the index of that child. Otherwise, we remove k - 1 children from the circle starting at position start, wrapping around if we reach the end of the circle. We then recursively call the "circleGame" function with the new position start and the reduced number of children in the circle (since some children have been eliminated). Finally, we return the result of the recursive call plus k, again wrapping around if we reach the end of the circle.

The "circleGame" function can be called with the initial number of children in the circle (n) and a starting position of 0. The function will recursively remove children from the circle until only one child remains. The final result will be the index of this last child.

Code:

Here's the Python code for the recursive function:

def circleGame(n, k, start=0): if n == 1: return start else: to_remove = (start + k - 1) % n return (circleGame(n - 1, k, to_remove) + k) % n

We can then call this function with the given inputs in the problem:

winner = circleGame(n, k)

This will return the index of the last child remaining in the circle and solve the problem.

1