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:
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 <= 105The problem can be broken down using dynamic programming (DP). Let's denote dp[i] as the probability that the ith person gets his own seat. The first passenger (1st person) picking a seat will influence the probability calculation.
Base Cases:
dp[1] = 1 because the 1st person will always get his seat.dp[2] = 0.5 because the only two choices for the 1st person are seat 1 (resulting in seat 2 for passenger 2) or seat 2 (resulting in probability 0 for passenger 2).Recursive Case:
i > 2, if seat 1 is chosen by the 1st person, person i has the same problem as person i-1. Hence, please observe that the convergence values become dp[i]=dp[i-1], as further passengers choosing other emtpy seats propagate the recurrence.This implementation makes use of the observed pattern that for n > 1, the probability stabilizes at 0.5 across large values of n. Essentially, we calculate the probability based on these conditions, speeding computation.
C++
Java
Python
C#
JavaScript
The function runs in O(1) time because the solution is calculated in constant time for either of the cases for any legal n. The space complexity is O(1) as only a fixed amount of extra space is used.
Through mathematical examination of the seat assignment problem, note that each passenger faces identical probability choices, independent of the initial convolutions by the first passenger. The nth person getting their seat can derive from recursive seated events indicating a general stasis at 0.5 beyond n=2.
This solution is formulated from recognizing repeated statistical expectation among larger sample sizes, affirming 0.5 likeliness past binary selection.
C++
Java
Python
C#
JavaScript
Constant O(1) time, while analytically driven conclusions confirm O(1) space.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | The function runs in O(1) time because the solution is calculated in constant time for either of the cases for any legal n. The space complexity is O(1) as only a fixed amount of extra space is used. |
| Mathematical Analysis Approach | Constant O(1) time, while analytically driven conclusions confirm O(1) space. |
How to EASILY solve LeetCode problems • NeetCode • 427,705 views views
Watch 9 more video solutions →Practice Airplane Seat Assignment Probability with our built-in code editor and test cases.
Practice on FleetCode