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/

LeetCode 1228 - Missing Number In Arithmetic Progression

https://www.geeksforgeeks.org/find-missing-number-arithmetic-progression/

Given an array that represents elements of arithmetic progression in order. One element is missing in the progression, find the missing number.

Examples:

Input: arr[]  = {2, 4, 8, 10, 12, 14}
Output: 6

Input: arr[]  = {1, 6, 11, 16, 21, 31};
Output: 26

static int findMissingUtil(int arr[], int low, 

                           int high, int diff)

{

    // There must be two elements

    // to find the missing

    if (high <= low)

        return Integer.MAX_VALUE;

  

    // Find index of 

    // middle element

    int mid = low + (high - low) / 2;

  

    // The element just after the 

    // middle element is missing. 

    // The arr[mid+1] must exist, 

    // because we return when

    // (low == high) and take

    // floor of (high-low)/2

    if (arr[mid + 1] - arr[mid] != diff)

        return (arr[mid] + diff);

  

    // The element just 

    // before mid is missing

    if (mid > 0 && arr[mid] - 

                   arr[mid - 1] != diff)

        return (arr[mid - 1] + diff);

  

    // If the elements till mid follow 

    // AP, then recur for right half

    if (arr[mid] == arr[0] + mid * diff)

        return findMissingUtil(arr, mid + 1, 

                               high, diff);

  

    // Else recur for left half

    return findMissingUtil(arr, low, mid - 1, diff);

}

  

// The function uses findMissingUtil() 

// to find the missing element in AP. 

// It assumes that there is exactly 

// one missing element and may give 

// incorrect result when there is no 

// missing element or more than one

// missing elements. This function also 

// assumes that the difference in AP is

// an integer.

static int findMissing(int arr[], int n)

{

    // If exactly one element is missing, 

    // then we can find difference of

    // arithmetic progression using 

    // following formula. Example, 2, 4, 

    // 6, 10, diff = (10-2)/4 = 2.

    // The assumption in formula is that 

    // the difference is an integer.

    int diff = (arr[n - 1] - arr[0]) / n;

  

    // Binary search for the missing 

    // number using above calculated diff

    return findMissingUtil(arr, 0, n - 1, diff);

}




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

数组 arr 中的值符合等差数列的数值规律：在 0 <= i < arr.length - 1 的前提下，arr[i+1] - arr[i] 的值都相等。

然后，我们从数组中删去一个 既不是第一个也不是最后一个的值。

给你一个缺失值的数组，请你帮忙找出那个被删去的数字。

样例

输入：arr = [5,7,11,13]
输出：9
解释：原来的数组是 [5,7,9,11,13]。

输入：arr = [15,13,12]
输出：14
解释：原来的数组是 [15,14,13,12]。

限制

• 3 <= arr.length <= 1000
• 0 <= arr[i] <= 10^5

(暴力枚举) $O(n)$

1. 首先求出 arr[1] - arr[0] 与 arr[n - 1] - arr[n - 2] 的差值 diff1 和 diff2。
2. 如果这两个差值不相等，若 diff1 == 2 * diff2，则缺失的值为 arr[0] + diff2；若 diff2 == 2 * diff1 则缺失的值为 arr[n - 1] - diff1。
3. 如果这两个差值相等，则说明差值就是 diff1（或 diff2），遍历一次数组，找到相邻两个元素不等的时候返回答案。
4. 如果没有找到，说明整个数组值全部相等，则直接返回 arr[0]。

时间复杂度

• 最多遍历一次数组，故时间复杂度为 $O(n)$。

空间复杂度

• 只需常数的额外空间。

int missingNumber(vector<int>& arr) { int n = arr.size(); int diff1 = arr[1] - arr[0]; int diff2 = arr[n - 1] - arr[n - 2]; if (diff1 != diff2) { if (diff1 == 2 * diff2) return arr[0] + diff2; else return arr[n - 1] - diff1; } for (int i = 1; i < n - 2; i++) if (arr[i + 1] - arr[i] != diff1) return arr[i] + diff1; return arr[0]; },

X.
https://www.codeleading.com/article/15242380716/

两个tricky的地方：

• 负数的整除不是truncate。（-3）//2 = -2 WHAT？？？
• 输入可以是同样的数，这样把任意一个同样的数可以补在任何的位置。所以result要赋值为arr【0】

def missingNumber(self, arr: List[int]) -> int: if arr[-1] > arr[0]: step = (arr[-1] - arr[0])//len(arr) else: step = (arr[0] - arr[-1])//len(arr) * -1 # tricky place 1。当然这里应该是整除的。 result = arr[0] # tricky place 2 for i in range(1, len(arr)): if arr[i] - arr[i-1] != step: result = arr[i-1] + step break return result

https://www.icode9.com/content-4-519698.html

• 1. 通过首尾元素算出该等差序列的差值, (tail-first)/len
• 1. 使用为2的窗口扫描整个数组, 选出前后两元素差值不等于之前整体差值的前一个元素
• 1. 输出前一个元素+差值

代码实现

暴力法 使用窗口遍历整个数组

class Solution {
    public int missingNumber(int[] arr) {
        int len = arr.length;
        // first, last 首尾两元素
        int first = arr[0], last = arr[len-1];
        // 该等差序列的整体等差
        int sub = (last-first) / len;

        for (int i = 0; i < len-1; i++) {
            // 一个为2的窗口 [i, i+1]
            int cur = arr[i], next = arr[i+1];
            // System.out.printf("cur:%d next:%d n1:%d\n", cur, next, cur+sub);
            // 如何前后元素差值不为等差, 那么前一个元素+等差 就是缺失的元素
            if (cur+sub != next) {
                return cur+sub;
            }
        }

        return 0;
    }

X. NlogN
https://www.cnblogs.com/seyjs/p/11713478.html

解题思路：题目很简单。先对数组排序，根据最大值和最小值即可求出公差，然后遍历数组，计算相邻元素的差，如果差不等于公差，即表示数字缺失。

    def missingNumber(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        arr.sort()
        diff = (arr[-1] - arr[0])/(len(arr))
        for i in range(len(arr)-1):
            if arr[i] + diff != arr[i+1]:
                return arr[i] + diff
        return arr[0]