Airplane Seat Assignment Probability
Problem
n passengers board a plane with exactly n seats. The first passenger has lost their ticket and picks a seat uniformly at random. Every other passenger takes their own assigned seat if it is free; otherwise they too pick a remaining seat at random. Return the probability that the n-th (last) passenger ends up in their own seat n.
n = 20.50000def nth_person_gets_nth_seat(n):
if n == 1:
return 1.0
return 0.5function nthPersonGetsNthSeat(n) {
if (n === 1) return 1.0;
return 0.5;
}class Solution {
public double nthPersonGetsNthSeat(int n) {
if (n == 1) return 1.0;
return 0.5;
}
}double nthPersonGetsNthSeat(int n) {
if (n == 1) return 1.0;
return 0.5;
}Explanation
This looks like a tricky simulation, but the answer is shockingly simple: for any n > 1 the probability is always 1/2, and for n == 1 it's 1.0. No loops, no recursion needed.
The intuition is a symmetry argument. The whole process really comes down to a race between two special seats: seat 1 (the lost-ticket passenger's own seat) and seat n (the last passenger's seat). Eventually someone is forced to pick one of those two.
If seat 1 gets taken first at any point, then by the time the last passenger boards, seat n is still free and they SUCCEED. If seat n gets taken first, they FAIL. Every random choice along the way treats these two seats identically, so each is equally likely to be grabbed first.
Because success and failure are perfectly balanced, the probability is exactly 0.5. The only exception is n == 1, where the single passenger must sit in their own seat, giving 1.0.
Example: n = 2. Passenger 1 picks seat 1 or seat 2 with equal chance. Only picking seat 1 leaves seat 2 free for passenger 2, so the probability is 1/2, matching the formula.