2682. Find the Losers of the Circular Game

EasyArrayHash TableSimulation
Leetcode Link

Problem Description

In this game involving n friends sitting in a circle, the play involves passing a ball around in a sequential and expanding pattern. The central rule is that with each turn, the distance in steps between the passer and the receiver increases linearly by k. That is, during the first turn, the ball is passed k steps away; on the second turn, it's 2 * k steps away, then 3 * k steps away on the third turn, and so on.

The key point is that the counting is cyclic and wraps around the circle. Once the count reaches the last friend, it continues from the first friend again. This cycle continues until a friend receives the ball for the second time, which signals the end of the game. The friends who never got the ball even once are the losers of the game.

The objective of this problem is to determine which friends lose the game, i.e., never receive the ball. This list of losers should be returned in ascending order of their numbered positions.

Intuition

To approach the solution, we can simulate the process of the game since the game’s rules are straightforward. If we follow the ball pass-by-pass, we can record who gets the ball and when the game ends.

Considering we are simulating the game's process, we have to track each friend who has received the ball. We can use an array, vis, of the same length as the number of friends (n). Each position in the array corresponds to a friend, where a value of True at an index means the friend at that position has received the ball, and False means they have not.

We keep two variables: i, which keeps the position of the current ball-holder, and p, which keeps the count of passes made thus far. Starting at position 0 (the 1st friend), with each turn, we mark the current position as visited (True), then move i by p * k steps forward (using modulo % operator to wrap around the circle), and increment p by 1 for the next pass. This continues until we return to a previously visited position, which means a friend got the ball for the second time, and the game ends.

After the game ends, we know who has had at least one turn with the ball. The remaining unvisited positions in the vis array correspond to friends who never got the ball—these are our losers. We output their corresponding numbers (incrementing by 1 since friend numbering is 1-based), filtered in ascending order.

The presented solution encapsulates this simulation in the circularGameLosers method and produces the result efficiently.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

A heap is a ...?

Solution Approach

The solution uses an elementary algorithm that is a direct implementation of the rules of the game. It simulates the passing of the ball amongst friends in a circle. The primary data structure is a list in Python (vis) used to keep track of which friends have received the ball.

Here is a step-by-step walkthrough of the algorithm:

  1. Initialize the vis list with False values since no one has received the ball initially.

    1vis = [False] * n

  2. Create two variables: i to represent the current position (starting from 0, which corresponds to the 1st friend) and p to represent the pth pass (starting from 1).

    1i, p = 0, 1

  3. Use a while loop to keep passing the ball until a friend receives it a second time, which is indicated when we hit a True in the vis list at position i.

  4. Inside the loop, mark the current position i as visited (True) in vis.

    1vis[i] = True

  5. Calculate the next position i to pass the ball to using the formula (i + p * k) % n, which accounts for the cyclic nature of passing the ball around the circle.

    1i = (i + p * k) % n

  6. Increment p by 1 to reflect the rules of the game for the next turn (p increments linearly each turn).

  7. When the loop ends (upon a second receipt), iterate through the vis list to collect the indices (friend numbers) where the value is still False, which means these friends did not receive the ball even once.

  8. For each unvisited index i, return i + 1 because friend numbering is 1-based, not 0-based. Produce the final output list using a list comprehension.

    1return [i + 1 for i in range(n) if not vis[i]]

The algorithm is a straightforward simulation and manages to keep time complexity at O(n) since each friend is visited at most once (every friend gets the ball at most once before the game ends). The use of modulo % for cyclic counting and a list comprehension for filtering out the losers contribute to the solution's conciseness and efficiency.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the relationship between a tree and a graph?

Example Walkthrough

Let's imagine a game with n = 5 friends sitting in a circle, and we'll use k = 2 to set the passing sequence. So, in this setup, the ball will be passed in increasing steps of 2 each turn.

  1. Let's start by creating the vis array to track who has received the ball, initializing all to False.

    1vis = [False, False, False, False, False]

  2. We'll start the pass from the 1st friend (indexed as 0) and initiate our pass count p at 1.

    1i, p = 0, 1  # Starting from the 1st friend

  3. As per the rules, the 1st friend passes the ball 2 steps away since p * k = 1 * 2 = 2. Hence, the ball goes to the 3rd friend (position i = (0 + 1*2) % 5 = 2).

    1vis[0] = True  # Mark the 1st friend as having received the ball
2i = (0 + 1 * 2) % 5  # Ball goes to the 3rd friend
3p += 1  # Increment pass counter for the next turn

    Now, vis = [True, False, False, False, False]

  4. Now on the second turn, p has incremented to 2, so the 3rd friend will pass it 4 steps ahead, which loops back around and lands on the 2nd friend (position i = (2 + 2*2) % 5 = 1).

    1vis[2] = True  # Mark the 3rd friend as having received the ball
2i = (2 + 2 * 2) % 5  # Ball goes to the 2nd friend
3p += 1

    Now, vis = [True, False, True, False, False]

  5. On the third turn, we have p = 3, the ball is passed to (1 + 3*2) % 5 = 0, which is back to the 1st friend. But since the 1st friend has already received the ball once (vis[0] = True), the game ends here.

  6. At this point, we can see from our vis array who hasn't received the ball:

    1vis = [True, False, True, False, False]

    The unvisited positions correspond to the 2nd, 4th, and 5th friends.

  7. We then return the list of losers (those who never received the ball), incrementing the index by one for the correct numbering:

    1losers = [i + 1 for i in range(5) if not vis[i]]  # [2, 4, 5]

In this example, the friends who lose this game are the 2nd, 4th, and 5th friends.

Solution Implementation

1from typing import List
2
3class Solution:
4    def circularGameLosers(self, n: int, k: int) -> List[int]:
5        # Create a list to keep track of visited positions
6        visited = [False] * n
7      
8        # Initialize index and step count
9        current_index, step = 0, 1
10      
11        # Loop and mark visited positions
12        while not visited[current_index]:
13            visited[current_index] = True
14          
15            # Calculate the next index by moving 'k' steps forward
16            # 'step' increases to simulate the change in the total number of players
17            current_index = (current_index + step * k) % n
18            step += 1
19      
20        # Return a list of non-visited indices (losers)
21        # Note: compensate for 0-indexed list by adding 1 to each index
22        return [index + 1 for index in range(n) if not visited[index]]
23
1class Solution {
2  
3    // Function that determines the positions that lose in the circular game
4    public int[] circularGameLosers(int n, int k) {
5        // Create an array to mark visited (eliminated) positions
6        boolean[] visited = new boolean[n];
7        int count = 0; // Count the number of visited (eliminated) positions
8        // Loop through the array, marking off eliminated positions
9        for (int index = 0, step = 1; !visited[index]; ++step) {
10            visited[index] = true; // Mark the current position as visited
11            ++count; // Increase the count of visited positions
12            // Calculate the next index based on the current index, step number and k
13            // Use modulo n to wrap around the circle
14            index = (index + step * k) % n;
15        }
16      
17        // Initialize an array to store the positions that did not lose (were not visited)
18        int[] losers = new int[n - count];
19        // Fill the array with the positions of those who did not lose
20        for (int i = 0, j = 0; i < n; ++i) {
21            if (!visited[i]) {
22                losers[j++] = i + 1; // Store the position (1-indexed) in the losers array
23            }
24        }
25      
26        return losers; // Return the array with the positions that lost in the game
27    }
28}
29
1#include <vector>
2#include <cstring>
3
4class Solution {
5public:
6    // Function simulates a circular game and returns a vector of losers' positions (1-indexed)
7    std::vector<int> circularGameLosers(int n, int k) {
8        std::vector<bool> visited(n, false); // Vector to keep track of visited positions
9
10        // Starting from the first position, mark visited positions
11        for (int currentPosition = 0, stepMultiplier = 1; 
12             !visited[currentPosition]; 
13             ++stepMultiplier) {
14            visited[currentPosition] = true;
15
16            // Compute the next position considering the steps taken
17            currentPosition = (currentPosition + stepMultiplier * k) % n;
18        }
19
20        std::vector<int> losers; // Initialize a vector to hold the losers
21        // Add unvisited positions (losers) to the vector. Positions are incremented by
22        // 1 because the problem is likely using 1-indexed positions.
23        for (int i = 0; i < n; ++i) {
24            if (!visited[i]) {
25                losers.push_back(i + 1);
26            }
27        }
28
29        return losers; // Return the vector of losers
30    }
31};
32
1function circularGameLosers(numPlayers: number, skipCount: number): number[] {
2    // Create an array to keep track of the players who have been eliminated.
3    const isEliminated = new Array(numPlayers).fill(false);
4  
5    // An array to hold the losers of the game, i.e., the eliminated players.
6    const losers: number[] = [];
7
8    // Loop to eliminate players until there is a last player standing.
9    // 'currentIndex' represents the current player in the loop, 'pass' increments each round to mimic the circular nature.
10    for (let currentIndex = 0, pass = 1; !isEliminated[currentIndex]; pass++) {
11        // Mark the current player as eliminated.
12        isEliminated[currentIndex] = true;
13
14        // Calculate the next player to be eliminated, wrapping around if necessary.
15        currentIndex = (currentIndex + pass * skipCount) % numPlayers;
16    }
17
18    // Collect the indexes of the players who were not eliminated.
19    for (let index = 0; index < isEliminated.length; index++) {
20        if (!isEliminated[index]) {
21            // Players are numbered starting from 1, hence adding 1 to the index.
22            losers.push(index + 1);
23        }
24    }
25
26    // Return the list of losers.
27    return losers;
28}
29
Not Sure What to Study? Take the 2-min Quiz：

How does quick sort divide the problem into subproblems?

Time and Space Complexity

Time Complexity

The given code generates a sequence of numbers to simulate a circular game where players are eliminated in rounds based on the number k. The while loop runs until it finds a previously visited index, which signifies the end of one complete cycle.

The worst-case time complexity occurs when the loop runs for all n players before any player is visited twice, so it will run for n iterations. Inside the loop, the main operations are:

  1. Setting the vis[i] value to True,
  2. Calculating the next index i using arithmetic operations, and
  3. Incrementing the value p.

The above operations are O(1) for each iteration.

Therefore, considering all the operations inside the loop, the worst-case time complexity of this code is O(n).

Space Complexity

The space complexity is determined by the amount of memory used in relation to the input size. The space used in the code comes from:

  1. The vis list, which is initialized to the size of the number of players n. This list takes up O(n) space.
  2. Variables i, and p, which take constant space, thus O(1).

There are no additional data structures that grow with the input size, thus the overall space complexity of the code is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫