Airplane Seat Assignment Probability Solution - Leetcode
Understand Leetcode Airplane Seat Assignment Probability With Brute Force and Optimal Solution
This document presents the solution to the problem Airplane Seat Assignment Probability - Leetcode.
Note: Make sure to go through the code comments as well. It’ll help you understand the concept better.
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:
1. Take their own seat if it is still available,
2. Pick other seats randomly when they find their seat occupied
What is the probability that the n-th person can get his own seat?
I’ll first try solving it by a brute force approach then I’ll move to a more optimal solution. While approaching towards the optimal solution, I’ll provide the approach behind the optimal solution.
If the first passenger takes his own seat, 1, then the other passengers will also be able to get their own seat because
of the first condition,Take their own seat if it is still available.
What if he doesn’t? The probability of him taking the correct seat would be 1/n where n is the total number of passengers.
Let’s start with n = 1.
Since there is only one seat the passenger can only get that seat so here the probability is 1.
if n is 2 then these two possibilities are there:
The 1st person taking wrong seat:
| 2 | 1 |
|---|
or
The 1st person taking the correct seat:
| 1 | 2 |
|---|
In the second arrangement the nth person(2nd person) was able to get the seat. So, here the probability is 1/2 or 0.5.
Let’s consider n = 3 now:
If the first person takes the correct seat then all the other passengers will take correct seats as well because those seats will be unoccupied. So one of the possibility could be:
| 1 | 2 | 3 |
|---|
if the first passenger takes the 2nd passenger’s seat then there are two possibilities:
| 2 | 1 | 3 |
|---|
| 2 | 3 | 1 |
|---|
if the first passenger takes the 3rd passenger’s seat then only one possibility remains:
| 3 | 2 | 1 |
|---|
So these are all the possibilities for when n = 3:
| 1 | 2 | 3 |
|---|---|---|
| 2 | 3 | 1 |
| 2 | 1 | 3 |
| 3 | 2 | 1 |
Here the probability is 2/4 = 1/2
This way we can find all the possibilities when n = 4 as well,
| 2 | 1 | 3 | 4 |
|---|---|---|---|
| 2 | 3 | 1 | 4 |
| 2 | 3 | 4 | 1 |
| 2 | 4 | 3 | 1 |
| 3 | 2 | 1 | 4 |
| 3 | 2 | 4 | 1 |
| 4 | 2 | 3 | 1 |
| 1 | 2 | 3 | 4 |
So, what have we done here:
- We’re allowing the 1st person to take each of the seats one by one.
- Then we allow the next person to take their seat, which can either be their allotted seat or any one of the remaining seat.
- We move ahead until all the seats are consumed
- Then we count all the arrangements that are possible, and the all the arrangements in which the nth person has their allotted seat.
I’ll create one array that will contain the seat allotment status for each of the pass.
// n is the number of passengers
func nthPersonGetsNthSeatBruteForce(n int) float64 {
if n == 1 {
return 1
}
// totalChances stores the count of all the passes that has happened
totalChances := 0
// bestChances stores the count of all the passes in which the n'th person got their correct seat
bestChances := 0
// through this loop the first person is getting the all the seats one by one
for i := 1; i <= n; i++ {
// seatsAllocated is an array that holds the seat allocation for each of the pass
var seatsAllocated = make([]int, n+1)
// the seat that will be taken by the 1st passenger(i) is set to 1
seatsAllocated[i] = 1
// and then the next person is allowed to take the next possible seat
nextPersonChance(n, 2, seatsAllocated, &totalChances, &bestChances)
}
return float64(bestChances) / float64(totalChances)
}
// nextPersonChance is called recursively
// here the parameter, nextN, holds the current passenger that is taking the seat
func nextPersonChance(n int, nextN int, seatsAllocated []int, totalChances, bestChances *int) {
if nextN == n {
*totalChances++
if 1 != seatsAllocated[nextN] {
*bestChances++
}
return
}
if 1 == seatsAllocated[nextN] {
// this if section is executed if the current passenger's allocated seat is already taken
for i := 1; i <= n; i++ {
if 1 != seatsAllocated[i] {
seatsAllocated[i] = 1
nextPersonChance(n, nextN+1, seatsAllocated, totalChances, bestChances)
seatsAllocated[i] = 0
}
}
} else {
// this else section is executed if the current passenger's allocated seat is available
seatsAllocated[nextN] = 1
nextPersonChance(n, nextN+1, seatsAllocated, totalChances, bestChances)
seatsAllocated[nextN] = 0
}
}
This is the brute force approach. Do let me know about the improvements that can be made here in this code so that it’s readability improves.
If we observe all the arrangements made for each n = 2,3,4 then we can find some patterns
when n = 2
| 2 | 1 |
|---|---|
| 1 | 2 |
when n = 3
| 2 | 3 | 1 |
|---|---|---|
| 2 | 1 | 3 |
| 3 | 2 | 1 |
| 1 | 2 | 3 |
when n = 4
| 2 | 1 | 3 | 4 |
|---|---|---|---|
| 2 | 3 | 1 | 4 |
| 2 | 3 | 4 | 1 |
| 2 | 4 | 3 | 1 |
| 3 | 2 | 1 | 4 |
| 3 | 2 | 4 | 1 |
| 4 | 2 | 3 | 1 |
| 1 | 2 | 3 | 4 |
when the 1st passenger takes the 2nd passenger’s seat then the count of all those arrangements is 2(n - 2)
- for n = 2 it’s 1
- for n = 3 it’s 2
- for n = 4 it’s 4
so, for n = 5 it’s 8
when the 1st passenger takes the 3nd passenger’s seat then the count of all those arrangements is 2(n - 3)
- for n = 3 it’s 1
- for n = 4 it’s 2
so, for n = 5 it’s 4
This means when n = 4 then the total number of arrangements can be:
- when 1st seat is taken by the 1st person = 1 (because there can only be one such arrangement, 1,2,3,4)
- when 2nd seat is taken by the 1st person = 2(n - 2) = 2(4 - 2) = 4
- when 3rd seat is taken by the 1st person = 2(n - 3) = 2(4 - 3) = 2
- when 4rd seat is taken by the 1st person = 1 (because there can only be one such arrangement, 4,2,3,1)
1 + 4 + 2 + 1 = 8
So, the formula for getting the total number of seat arrangements is: 1 + 2n-2 + 2n-3 + … + 2n-(n-1) + 1
Now, let’s look into the number of passes in which the n’th person gets the nth seat.
- You’ll find that if the 1st person takes the 1st seat then the last person will also get his own seat.
- If the last seat is taken by the 1st person the 1st seat will be taken by the 4th person and this is a failure scenario.
- For the rest of the cases you’ll find that the nth seat is taken by the nth passenger in half of the cases, ie., when 2nd seat taken by the 1st person, containing 4 such arrangements, then in half of such arrangements, 4th seat is taken by the 4th passenger(2,1,3,4 and 2,3,1,4)
1 + 0 + 2 + 1 = 4
So, the formula for getting the total number of seats arrangements in which nth person gets the last seat is: 1 + 0 + 2n-2/2 + 2n-3/2 + … + 2n-(n-1)/2
So our answer would be: (1 + 0 + 2n-2/2 + 2n-3/2 + … + 2n-(n-1)/2) / (1 + 2n-2 + 2n-3 + … + 2n-(n-1) + 1)
and, this value will always be equal to 1/2. 😎
This makes the solution to this problem to be:
func nthPersonGetsNthSeat(n int) float64 {
if n == 1 {
return 1
}
return 0.5
}
