#247MediumMath & Simulation· The Josephus Recurrence

Circle Elimination Winner

At a team-building event, `n` players stand in a circle and are numbered `1` to `n` clockwise. The game starts at player 1 and works like this: 1. Count `k` players clockwise, starting with the current one (so the current player is counted as 1). 2. The player where the count stops leaves the circle. 3. The next round starts with the player directly after the one who left, and the circle closes up. The last player standing wins. Return the number of the winner.

Input format

`n`: the number of players; `k`: the step size.

Output format

A single integer: the number (1 to n) of the winning player.

Examples

Input: n = 5, k = 2

Output: 3

Players leave in the order 2, 4, 1, 5, so player 3 wins.

Input: n = 6, k = 5

Output: 1

Players leave in the order 5, 4, 6, 2, 3 and player 1 is the last one.

Input: n = 1, k = 7

Output: 1

A single player wins immediately regardless of k.

Constraints

1 <= n <= 10^6
1 <= k <= 10^9

#simulation
#math
#recurrence
#josephus