Problem

n passengers board an airplane with exactly n seats. The first passenger has lost the ticket and picks a seat randomly. But after that, the rest of the passengers will:

  • Take their own seat if it is still available, and
  • Pick other seats randomly when they find their seat occupied

Return the probability that the nth person gets his own seat.

Examples

Example 1

1
2
3

Input: n = 1
Output: 1.00000
Explanation: The first person can only get the first seat.

Example 2

1
2
3

Input: n = 2
Output: 0.50000
Explanation: The second person has a probability of 0.5 to get the second seat (when first person gets the first seat).

Solution

Method 1 – Mathematical Induction

Intuition

The problem has a recursive structure: the probability that the last passenger gets their seat is always 1/2 for n > 1. This is because after the first passenger picks a random seat, the process repeats itself for the remaining passengers, except when the first or last seat is chosen.

Approach

  1. If there is only one passenger, they always get their seat (probability = 1).
  2. For n > 1:
  • The first passenger picks a seat at random.
  • If the first seat is chosen, everyone gets their own seat.
  • If the nth seat is chosen, the last passenger loses their seat.
  • If any other seat is chosen, the problem reduces to a smaller subproblem with n-1 seats.
  1. By induction, the probability converges to 0.5 for n > 1.

Code

1
2
3
4
5
6

class Solution {
public:
   double nthPersonGetsNthSeat(int n) {
      return n == 1 ? 1.0 : 0.5;
   }
};
1
2
3
4
5
6

func nthPersonGetsNthSeat(n int) float64 {
   if n == 1 {
      return 1.0
   }
   return 0.5
}
1
2
3
4
5

class Solution {
   public double nthPersonGetsNthSeat(int n) {
      return n == 1 ? 1.0 : 0.5;
   }
}
1
2
3
4
5

class Solution {
   fun nthPersonGetsNthSeat(n: Int): Double {
      return if (n == 1) 1.0 else 0.5
   }
}
1
2
3

class Solution:
   def nthPersonGetsNthSeat(self, n: int) -> float:
      return 1.0 if n == 1 else 0.5
1
2
3
4
5

impl Solution {
   pub fn nth_person_gets_nth_seat(n: i32) -> f64 {
      if n == 1 { 1.0 } else { 0.5 }
   }
}

Complexity

  • ⏰ Time complexity: O(1)
  • 🧺 Space complexity: O(1)