Problem

There are n friends that are playing a game. The friends are sitting in a circle and are numbered from 1 to n in clockwise order. More formally, moving clockwise from the ith friend brings you to the (i+1)th friend for 1 <= i < n, and moving clockwise from the nth friend brings you to the 1st friend.

The rules of the game are as follows:

1st friend receives the ball.

  • After that, 1st friend passes it to the friend who is k steps away from them in the clockwise direction.
  • After that, the friend who receives the ball should pass it to the friend who is 2 * k steps away from them in the clockwise direction.
  • After that, the friend who receives the ball should pass it to the friend who is 3 * k steps away from them in the clockwise direction, and so on and so forth.

In other words, on the ith turn, the friend holding the ball should pass it to the friend who is i * k steps away from them in the clockwise direction.

The game is finished when some friend receives the ball for the second time.

The losers of the game are friends who did not receive the ball in the entire game.

Given the number of friends, n, and an integer k, return the array answer, which contains the losers of the game in theascending order.

Examples

Example 1

1
2
3
4
5
6
7

Input: n = 5, k = 2
Output: [4,5]
Explanation: The game goes as follows:
1) Start at 1st friend and pass the ball to the friend who is 2 steps away from them - 3rd friend.
2) 3rd friend passes the ball to the friend who is 4 steps away from them - 2nd friend.
3) 2nd friend passes the ball to the friend who is 6 steps away from them  - 3rd friend.
4) The game ends as 3rd friend receives the ball for the second time.

Example 2

1
2
3
4
5

Input: n = 4, k = 4
Output: [2,3,4]
Explanation: The game goes as follows:
1) Start at the 1st friend and pass the ball to the friend who is 4 steps away from them - 1st friend.
2) The game ends as 1st friend receives the ball for the second time.

Constraints

  • 1 <= k <= n <= 50

Solution

Method 1 – Simulation with Visited Set

Intuition

We simulate the process of passing the ball, keeping track of which friends have received the ball. The losers are those who never receive the ball.

Approach

  1. Initialize a set or boolean array to track which friends have received the ball.
  2. Start from friend 1 (index 0). On the ith turn, pass the ball i * k steps ahead (modulo n).
  3. Stop when a friend receives the ball for the second time.
  4. The losers are those not in the set/array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    vector<int> circularGameLosers(int n, int k) {
        vector<bool> vis(n, false);
        int cur = 0, step = 1;
        while (!vis[cur]) {
            vis[cur] = true;
            cur = (cur + step * k) % n;
            ++step;
        }
        vector<int> ans;
        for (int i = 0; i < n; ++i) if (!vis[i]) ans.push_back(i+1);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func circularGameLosers(n, k int) []int {
    vis := make([]bool, n)
    cur, step := 0, 1
    for !vis[cur] {
        vis[cur] = true
        cur = (cur + step*k) % n
        step++
    }
    ans := []int{}
    for i, v := range vis {
        if !v { ans = append(ans, i+1) }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int[] circularGameLosers(int n, int k) {
        boolean[] vis = new boolean[n];
        int cur = 0, step = 1;
        while (!vis[cur]) {
            vis[cur] = true;
            cur = (cur + step * k) % n;
            ++step;
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; ++i) if (!vis[i]) ans.add(i+1);
        return ans.stream().mapToInt(i->i).toArray();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun circularGameLosers(n: Int, k: Int): IntArray {
        val vis = BooleanArray(n)
        var cur = 0; var step = 1
        while (!vis[cur]) {
            vis[cur] = true
            cur = (cur + step * k) % n
            step++
        }
        return (0 until n).filter { !vis[it] }.map { it+1 }.toIntArray()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def circularGameLosers(self, n: int, k: int) -> list[int]:
        vis = [False]*n
        cur = 0
        step = 1
        while not vis[cur]:
            vis[cur] = True
            cur = (cur + step*k) % n
            step += 1
        return [i+1 for i, v in enumerate(vis) if not v]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn circular_game_losers(n: i32, k: i32) -> Vec<i32> {
        let n = n as usize;
        let mut vis = vec![false; n];
        let (mut cur, mut step) = (0, 1);
        while !vis[cur] {
            vis[cur] = true;
            cur = (cur + step * k as usize) % n;
            step += 1;
        }
        (0..n).filter(|&i| !vis[i]).map(|i| (i+1) as i32).collect()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    circularGameLosers(n: number, k: number): number[] {
        const vis = Array(n).fill(false);
        let cur = 0, step = 1;
        while (!vis[cur]) {
            vis[cur] = true;
            cur = (cur + step * k) % n;
            ++step;
        }
        const ans: number[] = [];
        for (let i = 0; i < n; ++i) if (!vis[i]) ans.push(i+1);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), since each friend is visited at most once.
  • 🧺 Space complexity: O(n), for the visited array.