0213MediumArrayMathRecursionQueueSimulation

Last Apprentice at the Kiln

Tracked in this browser only

Trains the technique from

LeetCode 1823Find the Winner of the Circular Game

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def last_apprentice_at_the_kiln(apprentices: int, step: int) -> int:

Java

public int lastApprenticeAtTheKiln(int apprentices, int step)

The intended approach

Time O(n)Space O(1)

Track the winner's position rather than the ring. In a ring of one the survivor sits at offset 0 from wherever counting starts. Growing the ring by one seat moves the start of counting `step` seats back relative to the survivor, so the survivor's offset in a ring of `size` is the previous offset plus `step`, taken around `size`. Loop the ring sizes upward from two to `apprentices` and add one at the end to turn the offset into a seat number.

Pythonentry point: last_apprentice_at_the_kiln

def last_apprentice_at_the_kiln(apprentices, step):
    # Time: O(n) -- one pass over ring sizes 2..n.
    # Space: O(1).
    spot = 0
    size = 2
    while size <= apprentices:
        spot = (spot + step) % size
        size += 1
    return spot + 1

The obvious version

Hold the seat numbers in a list and act the thinning out: step the cursor forward by the count, remove that entry, and keep going until one entry is left.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_last_apprentice_at_the_kiln(apprentices, step):
    ring = list(range(1, apprentices + 1))
    at = 0
    while len(ring) > 1:
        at = (at + step - 1) % len(ring)
        ring.pop(at)
    return ring[0]

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in