find-the-losers-of-the-circular-game

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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

The rules of the game are as follows:

<code>1st</code> friend receives the ball.

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

In other words, on the <code>ith</code> turn, the friend holding the ball should pass it to the friend who is <code>i * k</code> 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, <code>n</code>, and an integer <code>k</code>, return the array answer, which contains the losers of the game in the ascending order.

&nbsp;
Example 1:

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

Example 2:

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

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= k &lt;= n &lt;= 50</code></li>
</ul>

circularGameLosers

Find the Losers of the Circular Game

Find the Child Who Has the Ball After K Seconds

find-the-child-who-has-the-ball-after-k-seconds

找出 K 秒后拿着球的孩子

Array

Hash Table

Simulation

<code>n</code> 个朋友在玩游戏。这些朋友坐成一个圈，按 顺时针方向 从 <code>1</code> 到 <code>n</code> 编号。准确的说，从第 <code>i</code> 个朋友的位置开始顺时针移动 <code>1</code> 步会到达第 <code>(i + 1)</code> 个朋友的位置（<code>1 &lt;= i &lt; n</code>），而从第 <code>n</code> 个朋友的位置开始顺时针移动 <code>1</code> 步会回到第 <code>1</code> 个朋友的位置。

游戏规则如下：

第 <code>1</code> 个朋友接球。

<ul>
	<li>接着，第 <code>1</code> 个朋友将球传给距离他顺时针方向 <code>k</code> 步的朋友。</li>
	<li>然后，接球的朋友应该把球传给距离他顺时针方向 <code>2 * k</code> 步的朋友。</li>
	<li>接着，接球的朋友应该把球传给距离他顺时针方向 <code>3 * k</code> 步的朋友，以此类推。</li>
</ul>

换句话说，在第 <code>i</code> 轮中持有球的那位朋友需要将球传递给距离他顺时针方向 <code>i * k</code> 步的朋友。

当某个朋友第 2 次接到球时，游戏结束。

在整场游戏中没有接到过球的朋友是 输家 。

给你参与游戏的朋友数量 <code>n</code> 和一个整数 <code>k</code> ，请按升序排列返回包含所有输家编号的数组 <code>answer</code> 作为答案。

&nbsp;

示例 1：

<pre>
输入：n = 5, k = 2
输出：[4,5]
解释：以下为游戏进行情况：
1）第 1 个朋友接球，第 1 个朋友将球传给距离他顺时针方向 2 步的玩家 —— 第 3 个朋友。
2）第 3 个朋友将球传给距离他顺时针方向 4 步的玩家 —— 第 2 个朋友。
3）第 2 个朋友将球传给距离他顺时针方向 6 步的玩家 —— 第 3 个朋友。
4）第 3 个朋友接到两次球，游戏结束。
</pre>

示例 2：

<pre>
输入：n = 4, k = 4
输出：[2,3,4]
解释：以下为游戏进行情况：
1）第 1 个朋友接球，第 1 个朋友将球传给距离他顺时针方向 4 步的玩家 —— 第 1 个朋友。
2）第 1 个朋友接到两次球，游戏结束。</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= k &lt;= n &lt;= 50</code></li>
</ul>