Guess Number Higher or Lower II
We are playing the Guessing Game. The game will work as follows:
- I pick a number between
1andn. - You guess a number.
- If you guess the right number, you win the game.
- If you guess the wrong number, then I will tell you whether the number I picked is higher or lower, and you will continue guessing.
- Every time you guess a wrong number
x, you will payxdollars. If you run out of money, you lose the game.
Given a particular n, return the minimum amount of money you need to guarantee a win regardless of what number I pick.
Example 1
Input
n = 10Output
16The worst case using an optimal strategy costs $16, so $16 is enough to guarantee a win.
Example 2
Input
n = 1Output
0There is only one possible number, so you can guess 1 and not have to pay anything.
Constraints
- 1 <= n <= 200