Guess Number Higher or Lower II

MediumDynamic Programminginterval dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A number between 1 and n has been picked. You guess numbers one at a time; after each wrong guess you are told whether the secret is higher or lower. Every **wrong** guess of x costs you x dollars, and a correct guess costs nothing. Return the smallest amount of money that guarantees you can find the secret no matter which number was picked, assuming you play optimally and the number is chosen adversarially. O(n^3) interval DP is fine for the given limits.

Examples

Input: n = 10
Output: 16
Guess 7 first, then keep splitting; the worst case over all secrets costs 16 with the best strategy.
Input: n = 1
Output: 0
There is only one possible number, so the first guess is right.

Constraints

  • `1 <= n <= 200`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More interval dp problems