Guess Number Higher or Lower II - Practice Coding Problems

Guess Number Higher or Lower II - Problem

We are playing the Guessing Game. The game will work as follows:

I pick a number between 1 and n.
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 pay x dollars.
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.

Input & Output

Example 1 — Small Range

$ Input: n = 3

› Output: 2

💡 Note: Optimal strategy: guess 2 first. If wrong, pay 2 dollars. In worst case, still need to guess between [1,1] or [3,3] which costs 0 more. Total worst case: 2 + 0 = 2.

Example 2 — Minimum Case

$ Input: n = 1

› Output: 0

💡 Note: Only one number to guess, so no wrong guesses possible. Cost is 0.

Example 3 — Larger Range

$ Input: n = 10

› Output: 16

💡 Note: For range [1,10], optimal strategy involves guessing numbers that minimize the worst-case cost across all possible target numbers.

Constraints

1 ≤ n ≤ 200

Visualization

Tap to expand

Understanding the Visualization

Game Setup

Target number chosen from range [1,n], we must guarantee a win

Cost Calculation

Each wrong guess costs that number, we pay for mistakes

Optimal Strategy

Find minimum cost to handle the worst-case scenario

Key Takeaway

🎯 Key Insight: This is a minimax problem - minimize the maximum cost by choosing optimal guessing strategies using dynamic programming

Asked in

G Google 12 M Microsoft 8 a Amazon 6

The key insight is that this is a minimax problem where we need to minimize the maximum cost over all possible target numbers. For any guess k in range [i,j], the cost is k + max(cost[i,k-1], cost[k+1,j]). The optimal approach uses dynamic programming to build solutions bottom-up. Time: O(n³), Space: O(n²).

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Brute Force	O(2^n)	O(n)	Try all possible first guesses and recursively solve subproblems
Bottom-Up Dynamic Programming	O(n³)	O(n²)	Build solutions iteratively from smaller to larger ranges
Memoization (Top-Down DP)	O(n³)	O(n²)	Cache results of subproblems to avoid redundant calculations

Recursive Brute Force — Algorithm Steps

Try each number k in range [i,j] as first guess
Calculate cost = k + max(cost[i,k-1], cost[k+1,j])
Return minimum cost over all possible guesses

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Each Guess

For range [1,3], try guessing 1, 2, or 3 first

Calculate Subproblems

For each guess, solve left and right subranges recursively

Take Minimum

Choose the guess that minimizes worst-case cost

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int minCost(int i, int j) {
    if (i >= j) return 0;
    
    int result = INT_MAX;
    for (int k = i; k <= j; k++) {
        int left = minCost(i, k - 1);
        int right = minCost(k + 1, j);
        int cost = k + (left > right ? left : right);
        if (cost < result) {
            result = cost;
        }
    }
    
    return result;
}

int solution(int n) {
    return minCost(1, n);
}

int main() {
    int n;
    scanf("%d", &n);
    
    int result = solution(n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Each recursive call branches into two subproblems, creating exponential growth

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth can go up to n levels

⚡ Linearithmic Space

78.2K Views

Medium Frequency

~35 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler