Find the Losers of the Circular Game

Let’s break down this statement.

  1. “We pre-populate the result array with all numbers”: This means that initially, we create an array and fill it with all the possible numbers. If we are discussing the context of the ‘circular game’, these numbers would represent all the friends. Each friend is represented by a distinct number in this array.

  2. “and set a number to zero once visited.”: In the context of the ‘circular game’, a friend “visits” when they receive the ball. So, each time a friend gets the ball, we mark their corresponding number in the array as zero. This helps keep track of which friends have already received the ball.

  3. “After the simulation, we return remaining non-zero numbers.”: After the game is over, we are interested in the friends who never got the ball. These are the friends whose corresponding numbers in the array were not set to zero (since they never received the ball). So, we look at our array and return the numbers that are still non-zero. These non-zero numbers represent the friends who never got the ball - the losers of the game.

We are using an array to keep track of who received the ball in the game. We initially assume that everyone will receive the ball and as the game progresses, we mark off those who do get the ball. At the end, we return the friends who never received the ball, hence they are the losers of the game.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

from itertools import accumulate

class Solution:
    def circularGameLosers(self, n: int, k: int) -> List[int]:
        # Create a set with numbers from 1 to n
        s = set([i for i in range(1, n + 1)])

        # Generate a sequence by adding up numbers from 0 to n-1
        sequence = accumulate([i for i in range(n)])

        # For each number in the sequence
        for mul in sequence:
            # Calculate the next number to be removed
            remove_num = k * mul % n + 1

            # If the number is not in the set, break the loop
            if remove_num not in s:
                break

            # Otherwise, remove the number from the set
            s.remove(remove_num)

        # Return the set of remaining numbers
        return s

Here’s a detailed breakdown of how this function works:

  1. It creates a set s containing all integers from 1 to n inclusive. In Python, a set is a collection of unique elements.

  2. It generates a sequence of numbers by successively adding numbers from 0 to n-1. The accumulate function from Python’s itertools module is used for this.

  3. For each number mul in the generated sequence, it calculates the number to be removed from the set s. This is done by multiplying mul by k and then taking the remainder after dividing by n. The result is incremented by 1 because the numbers in the set s start from 1.

  4. If the number to be removed is not in the set s, it breaks the loop and stops removing numbers.

  5. If the number to be removed is in the set s, it removes the number from the set.

  6. Finally, it returns the set s, which contains the numbers that have not been removed.

This function has a time complexity of O(n), where n is the input parameter, because it iterates over a sequence of length n. It has a space complexity of O(n) because it creates a set and a list, both of length n.

Here’s a detailed breakdown of the Python solution:

1
2
3

class Solution:
    def circularGameLosers(self, n: int, k: int) -> List[int]:
        s = set([i for i in range(1, n + 1)])

This code defines a class Solution with a method circularGameLosers, which takes two parameters, n and k. Inside the method, a set s is created that contains integers from 1 to n inclusive.

1

        for mul in accumulate([i for i in range(n)]):

The accumulate function generates a list where each element is the sum of the current and all previous elements in the range from 0 to n-1. The for loop iterates over each element in this list.

1
2

            if k * mul % n + 1 not in s:
                break

This code calculates the product of k and mul (the current element from the accumulated list), then takes the modulus by n and increments it by 1. If the resulting number is not in the set s, the loop is broken and we stop removing numbers.

1

            s.remove(k * mul % n + 1)

If the calculated number is in the set s, this line of code removes it from the set.

1

        return s

Finally, the method returns the set s, which contains the remaining numbers after the removal process.

This function simulates a circular game, where players numbered 1 to n are removed from the game in a certain order, determined by k and mul. The remaining players (those who were not removed) are returned as the output.

Beginner Friendly Version

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

from typing import List
from itertools import accumulate

class Solution:
    def circularGameLosers(self, n: int, k: int) -> List[int]:
        # Create a set of all the players
        s = set()
        for i in range(1, n + 1):
            s.add(i)

        # Create a list of multiples of k
        mul_list = []
        for i in range(n):
            mul_list.append(i)

        # Accumulate the list
        accum_list = accumulate(mul_list)

        # Run the game
        for mul in accum_list:
            index = k * mul % n + 1
            if index not in s:
                break
            else:
                s.remove(index)

        return list(s)

In this code, we first initialize a set containing all the friends. Then we create a list of multiples which we are going to use in the game process. The accumulate function returns accumulated sums. We then start the game and for each accumulated multiple, we calculate the index of the friend who gets the ball and remove them from the set if they are still in the game (i.e., they are in the set). The game ends when the ball reaches a friend who is already out of the game (i.e., they are not in the set). Finally, we return the list of losers which are the friends remaining in the set.