Airplane Seat Assignment Probability

Problem Description

Given n passengers boarding an airplane with exactly n seats, the first passenger has lost their ticket and chooses a seat randomly. Subsequent passengers will sit in their assigned seat if available; otherwise, they will choose a random seat. The task is to return the probability that the nth passenger ends up in their own seat.

Key Insights

• The first passenger's choice affects the seating arrangement for all subsequent passengers.
• If the first passenger takes their own seat, every passenger will sit in their assigned seat, leading to a probability of 1 for the nth passenger.
• If the first passenger takes the nth passenger's seat, the nth passenger will not get their seat, leading to a probability of 0.
• The probability oscillates between these two extremes based on the choices made by the first passenger.
• The underlying pattern leads to the conclusion that the probability for the nth passenger to sit in their own seat is always 0.5 for n > 2.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

The problem can be analyzed using a combinatorial approach. The key insight is that the final outcome for the nth passenger is determined by the random choice of the first passenger. The scenarios can be summarized as:

1. If the first passenger chooses their own seat, the nth passenger will definitely get their seat.
2. If the first passenger chooses the nth passenger's seat, the nth passenger will not get their seat.
3. For all other choices, the problem resets, leading to a recursive situation that ultimately reveals that the probability stabilizes to 0.5 for n >= 2.

Thus, the solution can be summarized with a simple conditional check on n:

Code Solutions