Find the Losers of the Circular Game

Difficulty: Easy | Acceptance: 50.00% | Paid: No Topics: Array, Hash Table, Simulation

You are given an integer n, the number of friends playing the game, and an integer k. The game is played as follows:

1. The 1st friend receives the ball.
2. In the ith turn, the friend holding the ball passes it to the friend k * i steps ahead in the circle. The counting wraps around the circle.
3. The game ends when a friend receives the ball for the second time.

Return an array answer containing the losers of the game in increasing order.

• Examples
• Constraints
• Simulation with Boolean Array
• Simulation with HashSet
• Simulation with Bitmask

Examples

Example 1:

Input: n = 5, k = 2
Output: [4,5]
Explanation:
The game goes as follows:
1) Start at friend 1, pass 2*1 = 2 steps to friend 3.
2) Friend 3 passes 2*2 = 4 steps to friend 5.
3) Friend 5 passes 2*3 = 6 steps to friend 4.
4) Friend 4 passes 2*4 = 8 steps to friend 3.
Friend 3 receives the ball for the second time, so the game ends.
Friends 4 and 5 never received the ball.

Example 2:

Input: n = 4, k = 4
Output: [2,3,4]
Explanation:
The game goes as follows:
1) Start at friend 1, pass 4*1 = 4 steps to friend 1.
Friend 1 receives the ball for the second time, so the game ends.
Friends 2, 3, and 4 never received the ball.

Constraints

2 <= n <= 50
1 <= k <= 50

Simulation with Boolean Array

Intuition We can simulate the game process step-by-step. We maintain a boolean array to track which friends have received the ball. We iterate through the turns, calculating the next friend to receive the ball using the formula (current + k * i) % n. If we encounter a friend who has already received the ball, the game ends.

Steps

• Initialize a boolean array visited of size n with all values set to false.
• Initialize curr to 0 (representing friend 1) and i to 1.
• Loop while visited[curr] is false:
  • Mark visited[curr] as true.
  • Update curr to (curr + k * i) % n.
  • Increment i.
• After the loop, iterate through the visited array. For every index j where visited[j] is false, add j + 1 to the result list (converting from 0-based to 1-based indexing).
• Return the result list.

class Solution:
    def circularGameLosers(self, n: int, k: int) -> List[int]:
        visited = [False] * n
        curr = 0
        i = 1
        while not visited[curr]:
            visited[curr] = True
            curr = (curr + k * i) % n
            i += 1
        return [x + 1 for x in range(n) if not visited[x]]

Complexity

• Time: O(n) - In the worst case, we visit every friend once.
• Space: O(n) - We use an array of size n to track visited friends.
• Notes: This is the most straightforward approach and is very efficient given the constraints.

Simulation with HashSet

Intuition This approach is logically identical to the Boolean Array approach but uses a HashSet data structure to keep track of friends who have touched the ball. This aligns with the “Hash Table” topic tag.

Steps

• Initialize an empty HashSet seen.
• Initialize curr to 1 and i to 1.
• Loop while curr is not in seen:
  • Add curr to seen.
  • Calculate the next friend: curr = ((curr - 1 + k * i) % n) + 1. (Adjusting for 1-based indexing).
  • Increment i.
• Iterate from 1 to n. If a number is not in seen, add it to the result list.
• Return the result list.

class Solution:
    def circularGameLosers(self, n: int, k: int) -> List[int]:
        seen = set()
        curr = 1
        i = 1
        while curr not in seen:
            seen.add(curr)
            curr = (curr - 1 + k * i) % n + 1
            i += 1
        return [x for x in range(1, n + 1) if x not in seen]

Complexity

• Time: O(n) - We perform at most n insertions and lookups in the set.
• Space: O(n) - The set stores at most n integers.
• Notes: Slightly higher constant factor overhead compared to the boolean array due to hashing, but functionally equivalent.

Simulation with Bitmask

Intuition Since the constraint n is small (up to 50), we can optimize space by using a single integer as a bitmask to track visited friends. Each bit in the integer represents whether a specific friend has received the ball.

Steps

• Initialize an integer mask to 0.
• Initialize curr to 0 (0-based index) and i to 1.
• Loop while the bit at position curr is not set in mask:
  • Set the bit at position curr in mask.
  • Update curr to (curr + k * i) % n.
  • Increment i.
• Iterate from 0 to n-1. If the bit at position j is not set in mask, add j + 1 to the result list.
• Return the result list.

class Solution:
    def circularGameLosers(self, n: int, k: int) -> List[int]:
        mask = 0
        curr = 0
        i = 1
        while not (mask & (1 << curr)):
            mask |= (1 << curr)
            curr = (curr + k * i) % n
            i += 1
        return [x + 1 for x in range(n) if not (mask & (1 << x))]

Complexity

• Time: O(n) - We iterate at most n times.
• Space: O(1) - We only use a single integer for storage, regardless of n.
• Notes: This is the most space-efficient solution, suitable for systems with limited memory, though the boolean array is also perfectly acceptable for n=50.