Formatted question description: https://leetcode.ca/all/1227.html

1227. Airplane Seat Assignment Probability

Level

Medium

Description

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 passengers will:

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

What is the probability that the n-th person can get his own seat?

Example 1:

Input: n = 1

Output: 1.00000

Explanation: The first person can only get the first seat.

Example 2:

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).

Constraints:

  • 1 <= n <= 10^5

Solution

The answer is that, if n is 1, return 1, and otherwise return 0.5. Only one line of code is needed is using ternary expression.

The main difficulty is to explain why the answer is 0.5 for all values n >= 2. If n equals 2, the answer is quite straightforward. For n > 2, the explanation is as follows.

The first passenger has a probability 1 / n to select each seat. Let f(i) represent the probability that the n-th seat is occupied by others when the first passenger selects the i-th seat, where 1 <= i <= n. Obviously, f(1) = 0 and f(n) = 1.

Consider f(n - 1). Passengers from 2 to n - 2 can get their own seats, and passenger n - 1 may randomly select seat 1 or seat n, with 1/2 probability each. So f(n - 1) = 1/2.

Next consider f(n - 2). Passengers from 2 to n - 3 can get their own seats, and passenger n - 2 may randomly select seat 1, seat n - 1 or seat n, with 1/3 probability each. So f(n - 2) = 1/3 + 1/3 * f(n - 1) = 1/2.

Similarly, f(n - 3) = f(n - 4) = ... = f(2) = 1/2. So the total probability is 1 / n * (f(1) + f(2) + f(3) + ... + f(n)) = 1/2.

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

All Problems

All Solutions