Guess Number Higher or Lower II Solution in Java

Problem Description

Welcome to the world of guessing games, where you can feel like a psychic but with a lot less accuracy! The problem at hand is called “Guess Number Higher or Lower II.” Imagine you’re at a carnival, and there’s a game where you have to guess a number between 1 and n. The twist? You have to pay a certain amount of money for each guess, and you want to minimize your total expenditure while ensuring you always win.

So, if you guess a number and it’s wrong, you have to pay the amount of the number you guessed. If you guess correctly, you win the game (and maybe a stuffed animal). The challenge is to figure out the minimum amount of money you need to guarantee a win, regardless of the number chosen by the “carnival operator.”

It’s like trying to guess your friend’s favorite ice cream flavor, but every guess costs you a scoop of ice cream. Spoiler alert: you might end up broke and still not know if they like chocolate or vanilla!

Code Solution


class Solution {
  public int getMoneyAmount(int n) {
    int[][] mem = new int[n + 1][n + 1];
    Arrays.stream(mem).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
    return getMoneyAmount(1, n, mem);
  }

  // Returns the minimum money you need to guarantee a win of picking i..j.
  private int getMoneyAmount(int i, int j, int[][] mem) {
    if (i >= j)
      return 0;
    if (mem[i][j] != Integer.MAX_VALUE)
      return mem[i][j];

    for (int k = i; k <= j; ++k)
      mem[i][j] = Math.min(mem[i][j], Math.max(getMoneyAmount(i, k - 1, mem), 
                                               getMoneyAmount(k + 1, j, mem)) +
                                          k);

    return mem[i][j];
  }
}

Approach

The approach used in the code is a dynamic programming technique. The idea is to create a memoization table (mem) that stores the minimum amount of money needed to guarantee a win for any range of numbers from i to j. The function getMoneyAmount(i, j, mem) recursively calculates the minimum cost by trying every possible guess k in the range and taking the maximum of the costs of the two resulting ranges (left and right of k). The result is stored in the mem table to avoid redundant calculations.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n³)
Space Complexity	O(n²)

Real-World Example

Imagine you're at a game show where the host has a secret number between 1 and n. Each time you guess, you have to pay the number you guessed. If you guess too high or too low, you lose that money, and the host gives you a hint. The goal is to minimize your total spending while ensuring you eventually guess the right number. This problem mirrors that scenario perfectly!