Show problems as
Classic problem #1823MediumArrayMathRecursionQueueSimulation

Find the Winner of the Circular Game

Real-world version: Last Apprentice at the Kiln
Tracked in this browser only
Read Find the Winner of the Circular Game on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A pottery studio seats its trainees in a ring around the kiln. There are apprentices of them, numbered 1 upwards going clockwise, so the highest number sits shoulder to shoulder with number 1.

The tutor thins the ring one trainee at a time. Begin at apprentice 1 and count step seats clockwise, counting the apprentice you begin on as one. Whoever you finish on hands over their tools and leaves the ring. Begin the next count from the apprentice sitting immediately clockwise of the one who just left, count step seats again, and carry on the same way. Once the ring has grown short the counting simply keeps going round it, so the same apprentice can be counted more than once inside a single count. When only one apprentice is still seated, that apprentice keeps the wheel for the rest of the day.

Return the seat number of the apprentice who keeps the wheel.

Examples

Example 1

Input
apprentices = 7, step = 3
Output
4

The counts take out apprentices 3, 6, 2, 7, 5 and 1 in that order, and apprentice 4 is the one still seated.

Example 2

Input
apprentices = 9, step = 4
Output
1

The counts clear out apprentices 4, 8, 3, 9, 6, 5, 7 and last of all 2, which leaves apprentice 1 seated.

Example 3

Input
apprentices = 6, step = 1
Output
6

Each count stops on the apprentice it begins with, so seats 1 through 5 clear out in order and apprentice 6 keeps the wheel.

Constraints

  • 1 <= step <= apprentices <= 500

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def last_apprentice_at_the_kiln(apprentices: int, step: int) -> int:
Java
public int lastApprenticeAtTheKiln(int apprentices, int step)

More on the same topics