1227. Airplane Seat Assignment Probability.md

1227. Airplane Seat Assignment Probability

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

2. Solutions

Solution 1: Language: C One Line with Pure Mathematics

• Friday, 20 November, 2020
• Time Complexity: $O(1)$
• Space Complexity: $O(1)$
• Runtime: 0 ms, faster than 100.00% of C online submissions for Airplane Seat Assignment Probability.
• Memory Usage: 5.7 MB, less than 22.22% of C online submissions for Airplane Seat Assignment Probability.

double nthPersonGetsNthSeat(int n){
    return n > 1 ? 0.5 : 1;
}

Solution 2: Language: Python Python Version of "Solution 1"

• Friday, 20 November, 2020
• Time Complexity: $O(1)$
• Space Complexity: $O(1)$
• Runtime: 12 ms, faster than 92.94% of Python online submissions for Airplane Seat Assignment Probability.
• Memory Usage: 13.4 MB, less than 40.00% of Python online submissions for Airplane Seat Assignment Probability.

class Solution(object):
    def nthPersonGetsNthSeat(self, n):
        """
        :type n: int
        :rtype: float
        """
        if n > 1:
            return 0.5
        else:
            return 1.0

3. Further Mathematics/Computing Bonus

• Use dynamic programming to solve this problem.
• One more step:
  1. Calculate the average amount of passengers who picked the wrong seat under given conditions.
  2. Calculate the average amount of passengers who picked the wrong seat if the first passenger picked the wrong seat.
  3. If all of passengers lost their ticket, and they would pick a seat randomly, just like the first passenger. Under this circumstance,
     • what is the probability that the n^th person can get his own seat?
     • Calculate the average amount of passengers who picked the wrong seat.
  4. Calculate the probability that all passengers picked a wrong seat.
• Add a mathematics solution and idea.