Created
April 19, 2021 01:08
-
-
Save humpydonkey/73603302687433f703622cb72a2dd3c0 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
// f(n) = 1 / n + (n - 2) / n * f(n - 1) | |
// | |
// 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) ) | |
// Now, you can easily get | |
// f(1) = 1 | |
// f(2) = 1/2 | |
// f(3) = 1/2 | |
// ... | |
public double nthPersonGetsNthSeat(int n) { | |
return n == 1 ? 1.0d : .5d; | |
} | |
public double nthPersonGetsNthSeat_naive(int n) { | |
if (n == 1) return 1.0d; | |
return 1d / n + (n - 2d) / n * nthPersonGetsNthSeat(n - 1); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment