1227. Airplane Seat Assignment Probability
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 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.
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 <= 105
Solutions
Solution 1: Mathematics
Let $f(n)$ represent the probability that the $n$th passenger will sit in their own seat when there are $n$ passengers boarding. Consider from the simplest case:
When $n=1$, there is only 1 passenger and 1 seat, so the first passenger can only sit in the first seat, $f(1)=1$;
When $n=2$, there are 2 seats, each seat has a probability of 0.5 to be chosen by the first passenger. After the first passenger chooses a seat, the second passenger can only choose the remaining seat, so the second passenger has a probability of 0.5 to sit in their own seat, $f(2)=0.5$.
When $n>2$, how to calculate the value of $f(n)$? Consider the seat chosen by the first passenger, there are three cases.
-
The first passenger has a probability of $\frac{1}{n}$ to choose the first seat, then all passengers can sit in their own seats, so the probability of the $n$th passenger sitting in their own seat is 1.0.
-
The first passenger has a probability of $\frac{1}{n}$ to choose the $n$th seat, then the second to the $(n-1)$th passengers can sit in their own seats, the $n$th passenger can only sit in the first seat, so the probability of the $n$th passenger sitting in their own seat is 0.0.
-
The first passenger has a probability of $\frac{n-2}{n}$ to choose the remaining seats, each seat has a probability of $\frac{1}{n}$ to be chosen. Suppose the first passenger chooses the $i$th seat, where $2 \le i \le n-1$, then the second to the $(i-1)$th passengers can sit in their own seats, the seats of the $i$th to the $n$th passengers are uncertain, the $i$th passenger will randomly choose from the remaining $n-(i-1)=n-i+1$ seats (including the first seat and the $(i+1)$th to the $n$th seats). Since the number of remaining passengers and seats is $n-i+1$, and 1 passenger will randomly choose a seat, the problem size is reduced from $n$ to $n-i+1$.
Combining the above three cases, we can get the recursive formula of $f(n)$:
$$ \begin{aligned} f(n) &= \frac{1}{n} \times 1.0 + \frac{1}{n} \times 0.0 + \frac{1}{n} \times \sum_{i=2}^{n-1} f(n-i+1) \ &= \frac{1}{n}(1.0+\sum_{i=2}^{n-1} f(n-i+1)) \end{aligned} $$
In the above recursive formula, there are $n-2$ values of $i$, since the number of values of $i$ must be a non-negative integer, so the above recursive formula only holds when $n-2 \ge 0$ i.e., $n \ge 2$.
If you directly use the above recursive formula to calculate the value of $f(n)$, the time complexity is $O(n^2)$, which cannot pass all test cases, so it needs to be optimized.
Replace $n$ with $n-1$ in the above recursive formula, you can get the recursive formula:
$$ f(n-1) = \frac{1}{n-1}(1.0+\sum_{i=2}^{n-2} f(n-i)) $$
In the above recursive formula, there are $n-3$ values of $i$, and the above recursive formula only holds when $n-3 \ge 0$ i.e., $n \ge 3$.
When $n \ge 3$, the above two recursive formulas can be written as follows:
$$ \begin{aligned} n \times f(n) &= 1.0+\sum_{i=2}^{n-1} f(n-i+1) \ (n-1) \times f(n-1) &= 1.0+\sum_{i=2}^{n-2} f(n-i) \end{aligned} $$
Subtract the above two formulas:
$$ \begin{aligned} &~~~ n \times f(n) - (n-1) \times f(n-1) \ &= (1.0+\sum_{i=2}^{n-1} f(n-i+1)) - (1.0+\sum_{i=2}^{n-2} f(n-i)) \ &= \sum_{i=2}^{n-1} f(n-i+1) - \sum_{i=2}^{n-2} f(n-i) \ &= f(2)+f(3)+...+f(n-1) - (f(2)+f(3)+...+f(n-2)) \ &= f(n-1) \end{aligned} $$
After simplification, we get the simplified recursive formula:
$$ \begin{aligned} n \times f(n) &= n \times f(n-1) \ f(n) &= f(n-1) \end{aligned} $$
Since we know that $f(1)=1$ and $f(2)=0.5$, therefore when $n \ge 3$, according to $f(n) = f(n-1)$, we know that for any positive integer $n$, $f(n)=0.5$. And since $f(2)=0.5$, therefore when $n \ge 2$, for any positive integer $n$, $f(n)=0.5$.
From this, we can get the result of $f(n)$:
$$ f(n) = \begin{cases} 1.0, & n = 1 \ 0.5, & n \ge 2 \end{cases} $$
The time complexity of this solution is $O(1)$, and the space complexity is $O(1)$.
1 2 3 |
|
1 2 3 4 5 |
|
1 2 3 4 5 6 |
|
1 2 3 4 5 6 |
|
1 2 3 |
|
1 2 3 4 5 |
|