Airplane Seat Assignment Probability

Medium

Dynamic Programming Math Dynamic Programming

Problem

n passengers board an airplane with exactly n seats. The first passenger has lost their ticket and picks a seat randomly. After that, the rest of the passengers will:

Take their own seat if it is still available, and
Pick other seats randomly when they find their seat occupied

Return the probability that the n^th person gets their own seat.

Constraints

1 <= n <= 10^5

Examples

Input: n = 1

Output: 1.00000

The first person can only get the first seat (which is also their own seat).

Input: n = 2

Output: 0.50000

The second person has a probability of 0.5 to get the second seat (when the first person randomly picks seat 1 instead of seat 2).

Loading...

Loading Python...