Budget for a Number-Guessing Game

# Budget for a Number-Guessing Game A hidden number is chosen from the integers `1` through `n`. After each guess, you learn whether the hidden number is larger or smaller, unless your guess is correct. A wrong guess of `x` costs `x` dollars. A correct guess costs nothing and ends the game. Return the minimum amount of money that guarantees you can find the number, regardless of which number was chosen. ### Function `int getMoneyAmount(int n)` ### Example 1 ```text Input: n = 4 Output: 4 ``` One strategy starts by guessing `3`. If the number is smaller, guess `1`, then identify `2` if needed. The most expensive outcome under this strategy costs `3+1 = 4`. If the number is larger than `3`, it must be `4`, with total cost `3`. No strategy guarantees success with less than `4`. ### Example 2 ```text Input: n = 3 Output: 2 ``` Guessing `2` first costs at most `2`; a wrong answer identifies either `1` or `3`. ### Example 3 ```text Input: n = 1 Output: 0 ``` ### Constraints - `1 <= n <= 200`. ### Clarifications You choose each next guess based on earlier feedback. The goal is a guarantee against the most expensive hidden-number outcome, not the average cost over a probability distribution. Return the required budget, rather than a sequence of guesses. ### What a Strong Answer Covers - The cost of correct and incorrect guesses. - Why the proposed budget covers every possible hidden number. - Why no smaller guaranteed budget suffices. - Correctness and resource bounds at the stated limit.