Welcome to Subscribe On Youtube
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; } } -
// OJ: https://leetcode.com/problems/airplane-seat-assignment-probability/ // Time: O(1) // Space: O(1) class Solution { public: double nthPersonGetsNthSeat(int n) { return n == 1 ? 1 : 0.5; } }; -
class Solution: def nthPersonGetsNthSeat(self, n: int) -> float: return 1 if n == 1 else 0.5 -
func nthPersonGetsNthSeat(n int) float64 { if n == 1 { return 1 } return .5 }