LeetCode 1227 - Airplane Seat Assignment Probability

https://leetcode.com/problems/airplane-seat-assignment-probability/

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

https://leetcode.com/problems/airplane-seat-assignment-probability/discuss/407781/Proof-by-mathematical-induction-that-answer-is-12-when-n-greater-2.

Q: Say if there are n passengers and the first passenger took the 3rd seat. Now, like you explained, there are n - 1 passengers and n - 1 seats left. But when the 2nd passenger comes in, he doesn't have 2 options to make it possible for the nth passenger to take the nth seat. Instead, he only has one option, which is to take the 2nd seat because it is not occupied by the first passenger. I don't see how that is the case of a subproblem of (n - 1). Could you shed some light please, thanks!
A: For any case, we can get rid of those sitting on own seats (except the first passenger) and get a problem of n' (= n - k, where k is the number of passengers sitting on own seats), then re-number (without changing the relative order) them as passenger 1, 2, ..., n', hence the result is in same form, the only difference is to change n to n'.
Except n' = 1, results for n' of other values are independent on n'. In short, changing from n to n' will not influence the result.

---

Part 1: [Java] 2 liners w/ explanation and analysis.

For the 1st passenger, there are 2 cases that the nth passenger could take the right seat:
1st passenger

1. Take his own seat, the probability is 1 / n;
2. Take a seat neither his own nor the one of the nth passenger, and the corresponding probability is (n - 2) / n; In addition, other passengers (except the nth one) should not occupy the nth seat;
   Now there are n - 1 passengers and n - 1 seats remaining, and the 2nd passenger, like the 1st one, have 2 options to make it possible the nth passenger take the right seat:
   a) take the 1st passenger's seat, the probability is 1 / (n - 1);
   b) Take a seat that is neither the 1st passenger's nor the nth passenger's, and the corresponding probability is ((n - 1) - 2) /( n - 1);
   Obviouly, we recurse to subproblem of (n - 1) .

Combined the above 2 cases, we have the following code:

    public double nthPersonGetsNthSeat(int n) {
        if (n == 1) return 1.0d;
        return 1d / n + (n - 2d) / n * nthPersonGetsNthSeat(n - 1);
    }

Analysis
Time: O(n), space: O(1).

---

Based on the code in part 1, we have the following formula:

f(n) = 1 / n + (n - 2) / n * f(n - 1)

Part2: Proof when n > 1, the f(n) is 1/2

1. n = 2, we have f(2) = 1/2; the assumption holds;
2. Suppose n = k we have f(k) = 1/2, when n = k + 1,

f(k + 1) = 1 / (k + 1) + (k + 1 - 2) / (k + 1) * f(k)
         = 2 / (2 * (k + 1)) + (k - 1) / (k + 1) * 1/2
         = 1 / 2

That is, f(k + 1) = 1 / 2 also holds.

From above 1 and 2, we complete the proof.

---

With the conclusion, it is easy to have 1 liners for Java and Python 3:

    public double nthPersonGetsNthSeat(int n) {
        return n == 1 ? 1.0d : .5d;
    }

    def nthPersonGetsNthSeat(self, n: int) -> float:
        return 1.0 if n == 1 else 0.5

X.https://leetcode.com/problems/airplane-seat-assignment-probability/discuss/407533/Python-from-O(n)-to-O(1)-with-detailed-explanation

Each round we have 3 choices:

1. the 1st person gets his/her own seat. (with probability 1/n). Then the n-th person is sure (with probability 1) to get the n-th seat.
2. the 1st person gets the n-th person's seat. (with probability 1/n). Then the n-th person cannot (with probability 0) get the n-th seat.
3. the 1st person gets a seat between 2 and n-1 (with probability (n-2)/n). Assume the 1st person gets a-th seat. Then in the next round, we have 3 choices again:
   3.1) if the a-th person gets 1st seat (with probability 1/(n-1)), then this is just like 1st and a-th person swap their seats, it never affect our result for the n-th person.
   3.2) if the a-th person gets n-th seat (with probability 1/(n-1)), game over.
   3.3) if the a-th person gets a seat which is not 1st or n-th, (with probability (n-1-2)/(n-1)), we jump into a loop.

Therefore the dp pattern is dp[i] = 1.0 / (i+1) + 0.0 / (i+1) + dp[i-1] * (i-1) / (i+1), with dp[0]=1 for the case there's only one person. If you manually calculate it you'll find dp[i] is always 1/2 except the base condition.

class Solution(object):
    def nthPersonGetsNthSeat(self, n):
        """
        :type n: int
        :rtype: float
        """
        # return 0.5 if n > 1 else 1.0
        
        dp = [0] * n
        dp[0] = 1.0
        for i in xrange(1, n):
            dp[i] = 1.0 / (i+1) +  dp[i-1] * (i-1) / (i+1) 
        return dp[-1]

https://www.cnblogs.com/onePunchCoder/p/11699121.html

n个用户依次登机就坐。第一个用户丢失了机票，将会随机选取一个座位，之后的乘客优先坐自己的座位，如果自己座位被占了则随机找寻一个座位就坐，求问第n个用户得到自己座位的概率。

2、分析与证明

• 假设有n个用户，本问题的答案为 f(n)。

• 如果第一个人随机到了自己的位置，那么后面的人一定按自己机票座位号入座。

• 如果第一个人随机到了第n个人的位置，那么第 n 个人得到自己座位的概率为0。

• 如果第一个人随机到了第2个人的位置，那么第 n 个人得到自己座位的概率为f(n-1)。

• 依次类推可得  f(n) = (1 + f(n-1) + f(n-2) + ... + f(2) + 0) / n ;

• 假设当 1< i <= k 时 f(i) = 1/2 , 容易证明f(k+1) = 1/2; 所以f(n) 在n > 1的时候恒等于 1/2 .

论证过程的代码实现如下

public double nthPersonGetsNthSeat(int n) {
        if(n==1) return 1.0;
        double[] dp = new double[n];
        double sum = 0;
        for (int i = 1; i < n; i++) {
            dp[i] =  (1 + sum) / (i + 1);
            sum += dp[i];
        }
        return dp[n - 1];
    }

https://www.acwing.com/solution/LeetCode/content/5445/