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

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

Code

[{"language":"C++","code":"class Solution {\npublic:\n    vector<int> circularGameLosers(int n, int k) {\n        vector<bool> vis(n, false);\n        int cur = 0, step = 1;\n        while (!vis[cur]) {\n            vis[cur] = true;\n            cur = (cur + step * k) % n;\n            ++step;\n        }\n        vector<int> ans;\n        for (int i = 0; i < n; ++i) if (!vis[i]) ans.push_back(i+1);\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">    vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">> </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">circularGameLosers</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> n</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> k</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">        vector</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;bool></span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> vis</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(n, </span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\">false</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">);</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> cur </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> 0</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, step </span><span style=\"color:#D73A49;--shiki-dark

Related Tags