0654MediumMathRecursion

Last Ticket on the Table

Tracked in this browser only

Trains the technique from

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.

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 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_ticket(n: int) -> int:

Java

public int lastTicket(int n)

The intended approach

Time O(log n): each sweep halves the number of tickets left.Space O(1): three running numbers and a direction flag.

The survivors of any sweep are always evenly spaced, so the row can be described by three numbers: the ticket at its left end, the constant gap between neighbours, and how many tickets remain. A sweep halves the count, rounding down, and doubles the gap. A left-to-right sweep always removes the leftmost ticket, so the left end moves up by one gap; a right-to-left sweep removes the leftmost ticket only when an odd number of tickets remains. Repeating this until one ticket remains takes about log2(n) steps.

Pythonentry point: last_ticket

def last_ticket(n):
    # Track only the number on the leftmost surviving ticket, the gap between
    # survivors, and how many survive. O(log n) time, O(1) space.
    head = 1
    gap = 1
    left = n
    from_left = True
    while left > 1:
        # A left-to-right sweep always takes the leftmost ticket. A right-to-left
        # sweep takes it only when an odd number of tickets is on the table.
        if from_left or left % 2 == 1:
            head += gap
        left //= 2
        gap *= 2
        from_left = not from_left
    return head

The obvious version

Hold the actual row as a list. For a right-to-left sweep, reverse the list, keep every second entry starting from the second, then reverse back; for a left-to-right sweep, keep every second entry directly. Repeat until one entry remains.

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_ticket(n):
    row = list(range(1, n + 1))
    from_left = True
    while len(row) > 1:
        if not from_left:
            row.reverse()
        row = [row[i] for i in range(len(row)) if i % 2 == 1]
        if not from_left:
            row.reverse()
        from_left = not from_left
    return row[0]

How this problem was checked

Reference solution executed against 13 test cases — 13 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