Elimination Game
Real-world version: Last Ticket on the TableThe statement here is our own: the same inputs, outputs and technique.
Raffle tickets numbered 1 through n are laid out on a table in a single row, in increasing order. A steward then thins the row out in sweeps.
The first sweep runs from the left end to the right end: the steward takes the first ticket still on the table, leaves the next one, takes the one after that, and so on to the far end. The second sweep runs from the right end back to the left, following the same take-one-leave-one rhythm starting with the ticket at the right end. Sweeps keep alternating direction like this until a single ticket is left.
Return the number printed on that last ticket.
Examples
Example 1
- Input
- n = 6
- Output
- 4
The first sweep takes 1, 3 and 5, leaving 2, 4, 6. The second sweep starts at the right end, taking 6 and then 2, so ticket 4 is the one left.
Example 2
- Input
- n = 24
- Output
- 14
The four sweeps leave 2, 4, 6, ..., 24; then 2, 6, 10, 14, 18, 22; then 6, 14, 22; and finally ticket 14 on its own.
Example 3
- Input
- n = 8
- Output
- 6
The first sweep leaves 2, 4, 6, 8. The second runs from the right, taking 8 and then 4, which leaves 2 and 6. The third runs from the left and takes 2, so ticket 6 is the survivor.
Constraints
- 1 <= n <= 10^9
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.
def last_ticket(n: int) -> int:public int lastTicket(int n)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 13 test cases: 13 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's