Last Viewer in the Right Seat

Medium

A small cinema hall has viewers seats, and exactly viewers tickets were sold, each for its own seat. Viewers walk in one at a time in ticket order. The first viewer has lost their ticket and sits in a random seat, all seats being equally likely. Everyone after that takes their own seat if it is free; if it is taken, they pick a random one among the seats still free. Return the probability that the last viewer ends up in their own seat.

Example 1

viewers=1 → 1

One viewer and one seat: they cannot miss their own.

Example 2

viewers=2 → 0.5

The first viewer picks their own seat (then the second gets theirs) or the other one (then the second ends up in the first viewer's seat) with equal chance, so 0.5.

Example 3

viewers=4 → 0.5

Constraints

1 ≤ viewers ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Brainteaser Math Dynamic Programming Probability and Statistics

Similar problems

Which Pot Runs Dry First Medium Chance of Not Going Over Medium Odds of Exactly That Many Heads Medium Take From Any Pile Medium Two-Letter Tiles, No Triples Medium

Input

viewers=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 29 tests on the server, hidden ones included.