Leetcode 1227: Airplane Seat Assignment Probability
There are
n passengers boarding an airplane with n seats. The first passenger has lost their ticket and picks a random seat. The remaining passengers sit in their assigned seat if available or pick a random seat if their assigned seat is taken. Return the probability that the nth person gets their own seat.Problem
Approach
Steps
Complexity
Input: The input consists of a single integer `n` (1 <= n <= 10^5), representing the number of passengers and seats.
Example: n = 3
Constraints:
• 1 <= n <= 10^5
Output: The output is a floating-point number representing the probability that the nth person sits in their own seat.
Example: 0.50000
Constraints:
• Return the answer with a precision of 5 decimal places.
Goal: The goal is to compute the probability that the last passenger sits in their own seat.
Steps:
• If there's only one passenger, they will always sit in their own seat (probability = 1).
• For more than one passenger, the probability follows a pattern where it is 0.5 for n >= 2.
Goal: The problem is designed for n ranging from 1 to 100,000, and the solution should efficiently compute the probability even for large n.
Steps:
• 1 <= n <= 10^5
Assumptions:
• The first passenger randomly selects a seat.
• Each subsequent passenger will either sit in their assigned seat or pick a random seat if theirs is taken.
• Input: n = 3
• Explanation: For three passengers, the first has a 50% chance of sitting in their assigned seat. If they don't, the third passenger has a 50% chance of sitting in theirs. The total probability for the nth person is 0.5.
Approach: The problem boils down to a simple observation: the probability of the nth person sitting in their seat is always 0.5 for n >= 2, and 1 for n = 1.
Observations:
• For n = 1, the answer is trivially 1.
• For n >= 2, the answer is always 0.5 based on a probabilistic pattern observed.
• This problem does not require complex simulations or recursive calculations for large n. We can directly return the result based on the value of n.
Steps:
• Check if n = 1, then return 1.
• For any n > 1, return 0.5.
Empty Inputs:
• No empty inputs are allowed.
Large Inputs:
• The solution should handle up to 10^5 efficiently.
Special Values:
• For n = 1, the probability is always 1.
Constraints:
• Ensure that the result is returned with a precision of 5 decimal places.
double nthPersonGetsNthSeat(int n) {
if(n == 1) return 1;
return 1/2.0;
}
1 : Function Definition
double nthPersonGetsNthSeat(int n) {
This is the function definition for `nthPersonGetsNthSeat`, which calculates the probability of the nth person sitting in their assigned seat.
2 : Conditional Check
if(n == 1) return 1;
If there is only one person (n == 1), they will always sit in their own seat, so the function returns 1.
3 : Return Value
return 1/2.0;
For all cases where n > 1, the probability is always 1/2 (50%) based on the problem's constraints, as the first person randomly chooses a seat, and from then on, the probability alternates.
Best Case: O(1)
Average Case: O(1)
Worst Case: O(1)
Description: The time complexity is constant since we are only checking if n is 1 or not.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant as no additional space is required beyond a simple check.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus