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

Difficulty: interview

Starter code:

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        

Solutions:
class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        return 1 / min(n, 2.0) 
        


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

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

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        if n == 1:
            return 1.0
        if n== 2:
            return 0.5
        return 0.5
        if n == 3:
            return (1/3 * 1 + 1/3 * 1/2 + 1/3 * 0) # pick his own seat, the nth person's seat, or...
        if n == 4:
            return (1/4 * 1 + 1/4 *(1/3*1+1/3*1/2 +1/3*0) +1/4 *(1/3*1+1/3*1 +1/3*0) + 1/4 * 0) # pick his own seat, the nth person's seat, or...
            
        return (1/n * 1 + (n-2)/n * self.nthPersonGetsNthSeat(n-2) + 1/n *0) 
      

      
        
        
        


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

import numpy as np


class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        if n == 1:
            return 1
        
        return 1/2


class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        
        if n==1:
            return 1
        
        s=0
        for i in range(1,n-1):
            s+=0.5/n
        
        return 1/n+s

import numpy as np
class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        '''
        if n==1:
            currentsum = 0
        else:
            currentsum = 1/n
            for i in range(2,n):
                currentsum = currentsum + currentsum/(n-i+1)
        return 1-currentsum
        '''
        if n==1:
            return 1
        else: return 1/2.0
                
            


class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        res = 1.0
        cur = 1.0
        
        for i in range(2, n + 1):
            res = (1 / i) * cur
            cur += res
            
        return res


class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        if n == 1:
            return 1
        return .5

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        res = 1.0
        t = 1.0
        
        for i in range(2, n + 1):
            res = (1 / i) * t
            t += res
        
        return res

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        
        if n==1:
            return 1
        
        if n==2:
            return 0.5
        
        dp=[0]*n
        dp[0]=1/n
        
        for i in range(1,n-1):
            dp[i]=0.5/n
        
        return sum(dp)

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        i = 0
        if n ==1:
            return 1
        
        notCorrect = 1/n
        
        for i in range(1,n-1):
            notCorrect*= (1.0 + 1.0/(n-i))
        
        
        return 1-notCorrect

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:

        
        i = 0
        if n ==1:
            return 1
        
        notCorrect = 1/n
        
        for i in range(1,n-1):
            notCorrect*= (1.0 + 1.0/(n-i))
        
        
        return 1-notCorrect

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        # if n == 1:
        #     return 1.0
        # else:
        #     return 0.5
        
        if n == 1:
            return 1.0
        sum_results = 0.0
        for i in range(2, n+1):
            p = 1/i * (1 + sum_results)
            sum_results += p
        return p

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        if n == 1:
            return(1)
        return(1/2)


class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        cur = 1
        for i in range(2, n+1):
            cur = 1/i + (i-2)/i*cur
        return cur

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        mem = {}
        mem[1] = 1.0
        mem[2] = 0.5
        for i in range(3, n+1):
            mem[i] = mem[i-1]
        
        return mem[n]

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        '''
        f(n) = 1/n                                    -> 1st person picks his own seat
            + 1/n * 0                                 -> 1st person picks last one's seat
            + (n-2)/n * (                            ->1st person picks one of seat from 2nd to (n-1)th
                1/(n-2) * f(n-1)                   -> 1st person pick 2nd's seat
                1/(n-2) * f(n-2)                  -> 1st person pick 3rd's seat
                ......
                1/(n-2) * f(2)                     -> 1st person pick (n-1)th's seat
            )

        => f(n) = 1/n * ( f(n-1) + f(n-2) + f(n-3) + ... + f(1) )
        '''
        if n==1:
            return 1.0
        if n==2:
            return 0.5
        dp = [1.0, 0.5]
        acc = 1.5
        for i in range(3, n+1):
            dp.append(acc/i)
            acc += dp[-1]
        return dp[-1]
    
        '''
        Formal proof with math solution
        when n > 2,
        f(n) = 1/n * ( f(n-1) + f(n-2) + ... + f(1) )
        f(n-1) = 1/(n-1) * (f(n-2) + f(n-3) + ... + f(1))

        because, the 2nd equation requires n-1 > 1
        So that

        n * f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(1)
        (n-1) * f(n-1) = f(n-2) + f(n-3) + ... + f(1)
        Substract both sides, we get

        n * f(n) - (n-1)*f(n-1) = f(n-1)

        => n * f(n) = n * f(n-1)
        => f(n) = f(n-1) = f(2) = 1/2 , when n > 2
        '''
        # return 1 if n==1 else 0.5


class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        if n == 1: return 1
        if n == 2: return 0.5
        result = 1.0
        curr = 1.0
        for i in range(2, n + 1):
            result = (1 / i) * curr
            curr += result
        return result
        


class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        if n == 1:
            return 1
        if n == 2:
            return 0.5
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 0.5
        acc = 1.5
        for i in range(3, n + 1):
            dp[i] = (1.0 / i) * acc
            acc += dp[i]
        return dp[-1]

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        if n == 1: return 1
        good = 0
        left = n
        uncenrtain = 1
        while left >= 2:
            # print(f'left={left}, good={uncenrtain}/{left}, uncenrtain={uncenrtain}*({left}-2)/{left}')
            good += uncenrtain/left
            uncenrtain = uncenrtain * (left-2)/left
            left -= 1
            # print('good=', good)
            
        return good

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        dp = [0] * (n + 1)
        if n > 0:
            dp[1] = 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] / 2 + (1 - dp[i - 1]) / 2
        return dp[n]

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        if n == 1:
            return 1
        else:
            # return 0.5
            dp = [0 for _ in range(n+1)]
            dp[n] = 1 / n
            for i in range(n-1, 1, -1):
                dp[i] = dp[i+1] / i + dp[i+1]
            return dp[2]

class Solution:
     
    def nthPersonGetsNthSeat(self, n: int) -> float:
        if n==1: return 1
        return 1/2


class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        p = [None, 1., 0.5]
        for i in range(2, n):
            prob = (i * p[i] + p[i]) / (i+1)
            p.append(prob)
        return p[n]


class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        if n == 1: return 1
        
        # let P(k) be the probability that the k-th person loses his seat
        # it can be shown that: P(k) = P(k-1)(1 + 1/(n-k+2))
        P = [None]*(n+1)
        P[2] = 1/n
        
        for i in range(3, n+1):
            P[i] = P[i-1]*(1 + 1/(n-i+2))
            
        return P[n]

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        D = [0]*n
        D[0] = 1.0
        for i in range(1,n):
            D[i] = 1/(i+1) + (i-1)/(i+1)*D[i-1]
        return D[-1]

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        if n==1:
            return 1
        elif n==2:
            return 0.5
        
        dp=[0]*(n)
        dp[0] = 1
        dp[1] = 0.5
        sum1 = dp[1]
        for i in range(2,n):
            dp[i] = 1/(i+1)+(1/(i+1))*sum1
            sum1 += dp[i] 
      
        return dp[-1]

import numpy as np
class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:

        if n==1:
            currentsum = 0
        else:
            currentsum = 1/n
            for i in range(2,n):
                currentsum = currentsum + currentsum/(n-i+1)
        return 1-currentsum

                
            


class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        if n == 1:
            return 1
        
        # Create a list of probablity of n-th person get his own seat under the situation 1-st person pick k-th seat
        pick = [1] + [0]*(n - 2) + [1]
        
        prob = 0
        for i in range(n-2, 0, -1):
            left = n - i
            pick[i] = 1/left + ((left-2)/left)*pick[i+1]
            prob += pick[i]
        
        return (prob+1)/n

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


class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        if n>1:
            return 0.5
        return 1

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        if n==1:
            return 1.00000
        else:
            return 0.50000


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