Problem Breakdown
We are given n passengers and exactly n seats on an airplane. The boarding process follows specific rules: Passenger 1 picks a random seat, while subsequent passengers take their assigned seat if available or pick randomly otherwise. We need to determine the probability that the last passenger (Passenger n) sits in Seat n.
- Input: An integer
n(). - Output: A float representing the probability between and .
- Constraints: The input is always positive integers, so we do not need to handle empty inputs or negative values.
Intuition
The core of this problem lies in tracking which seats are “contested” during the random selection process. Specifically, Seat 1 (assigned to Passenger 1) and Seat n (assigned to Passenger n) act as absorbing states for the displacement chain:
- If any displaced passenger picks Seat 1, everyone else gets their correct seat subsequently, including Passenger
n. Success is guaranteed. - If any displaced passenger picks Seat n before it’s filled by its owner, Passenger
nloses their seat immediately. Failure occurs. - Picking any other Seat () simply passes the “random choice” responsibility to another passenger without resolving the fate of Passenger
n.
Since all available seats are chosen uniformly at random when a displacement happens, and intermediate choices do not bias between Seat 1 and Seat n, these two specific seats have an equal probability of being selected first among the contested set. Thus, for any , the probability converges to exactly .
Approach
- Base Case Handling: If there is only one passenger (
n == 1), they must take Seat 1 by default since no other seats exist. The probability of getting their own seat is1.0. - General Logic: For any , the mathematical symmetry argument proves that regardless of how many passengers are displaced, the outcome depends solely on whether Seat 1 or Seat
ngets picked first by a random chooser (including Passenger 1). Since they are equally likely to be chosen in this symmetric process, we return0.5. - Implementation: We implement an check: if
n == 1, return1.0; otherwise, return0.5.
Complexity Analysis
- Time Complexity: . The solution performs a constant number of operations (a single comparison and return), independent of the magnitude of
nfor computation purposes. - Space Complexity: . We utilize no auxiliary data structures, recursion stacks, or memory proportional to input size beyond basic variables.
Solution
class Solution:
def nthPersonGetsNthSeat(self, n: int) -> float:
"""
Calculates the probability that the last passenger gets their own seat.
Args:
n (int): Number of passengers and seats.
Returns:
float: Probability value.
"""
# Base case: If there is only 1 passenger, they must get Seat 1.
if n == 1:
return 1.0
# For any n > 1, the probability converges to exactly 0.5 due to
# symmetry between Seat 1 and Seat n being chosen first in the random chain.
return 0.5
# Example usage for verification (not part of class submission)
if __name__ == "__main__":
print(Solution().nthPersonGetsNthSeat(1)) # Output: 1.0
print(Solution().nthPersonGetsNthSeat(2)) # Output: 0.5
Edge Cases Handled
n = 1: Explicitly handled to return1.0, matching Example 1 where the single passenger takes their only seat with certainty. This is a critical edge case as it differs from all other inputs ().- Large
n(): The logic handles large inputs without overflow or timeout, as no iteration occurs based on input size. - Constraints: Inputs are guaranteed to be , so division by zero or invalid index errors (like accessing seat -1) do not occur in the logical flow of this constant-time solution.