Guess Number Higher or Lower II Guess Number Higher or Lower II

Table of Contents

Problem Statement

“Guess Number Higher or Lower II” states that we are going to play a game that is called Guess Game. The game says that I pick a number from 1 to n. Whenever you guess the number which I have not picked, I m going to say you that you pick a number higher or lower.

And the important and interesting part is that if you chose the wrong number, let’s say x, then you are going to pay x units of the amount. You are supposed to win the game when you guess the correct number, i.e, that is the number I picked.

Example

n = 10, I pick 6.

First choose: You guess 2, it’s greater, go above than that. You will pay $2.

Second choose: You guess 4, it’s greater, go above than that. You will pay $4.

Third choose: You guess 5, it’s greater, go above than that. You will pay $5.

The game is over now because you have picked the correct number that is 6.

You end up paying $2 + $4 + $5 = $11.

Suppose, if you are given a number which is n ≥ 1, determine how much amount of money you should have so that you can assure that with this enough amount you are going to win this game.

Guess Number Higher or Lower II

Algorithm for Guess Number Higher or Lower II problem

1. Declare a 2-d array of size n+1.
2. Set output to the maximum value of an integer.
3. Set val to start + (end – start) / 2.
4. While val is less than or equal to end,
  1. Recursively call the function and find out the maximum between the values and Set table [start][end] to x + maximum of the number below the x value and number greater than the x value.
  2. Find out the minimum between the output and table[start][end] and update it into the output.
  3. Increase the value of x by 1.
4. Return table [start][end].

Explanation

We have given a number n so that we can find out enough amount of money from which we can assure our win, for this we can assume a number and perform operations on below of that number and above of that number. This code is going to recursively call its functions.

The problem expects you to minimize the maximum amount you would have to pay in order to win. Surely there is a different cost required to win in case of a different guess but our goal is to calculate the minimum amount needed to guess the number between 1…n,

result = Math.min(result, amount(i)) [returns the minimum of the inputs provided]

where amount(i) is the worst case possible amount for guessing number i.

Now, what is this worst case is when you assume 3.

You have picked 1, in the best case 1 might be the number you would have to guess, hence the amount(i)=0, but we are not bothered about that, we are concerned with the worst case, i,e 1 is not the picked number. Hence cost when 1 is picked is = 1+ cost from(2,3).

you picked 2, in the best case 2 is the answer and the cost is 0, but then in the worst case either 3 or either 1 is the answer, and upon guessing a number you always get to know that whether the picked number is greater or less than the number, hence we would know is 1 is the answer or 3 is the answer. hence the worst-case cost is 2.

Picking 3 the worst-case cost would be 3+ cost from(1,2). The final cost would be the minimum of all these worst-case costs. We have to do this recursively to get the answer and then memorize it.

Implementation

C++ program for Guess Number Higher or Lower II problem

#include<iostream>
#include<vector>

using namespace std;

int helper(int low,int high,vector<vector<int>> &dp)
{
    if(low>=high)
        return 0;
    if(dp[low][high]!=INT_MAX)
        return dp[low][high];
    for(int j=low; j<=high; j++)
    {
        dp[low][high]=min(dp[low][high],max(j+helper(low,j-1,dp),j+helper(j+1,high,dp)));
    }
    return dp[low][high];

}
int getMoneyAmount(int n)
{
    vector<vector<int>> dp(n+1,vector<int>(n+1,INT_MAX));
    return helper(1,n,dp);
}

int main()
{
    cout<<getMoneyAmount(10);
}

Java program for Guess Number Higher or Lower II problem

class guessNumber
{
    public static int getNumber(int n)
    {
        return guessNumberRec(new int[n+1][n+1], 1, n);
    }
    public static int guessNumberRec(int[][] arr, int left, int right)
    {
        if (left >= right)
        	return 0;
        if (arr[left][right] != 0)
        	return arr[left][right];

        arr[left][right] = Integer.MAX_VALUE;
        for (int a = left; a <= right; a++)
        {
            arr[left][right] = Math.min(arr[left][right], a + Math.max(guessNumberRec(arr, left, a - 1), guessNumberRec(arr, a + 1, right)));
        }
        return arr[left][right];
    }
    public static void main(String [] args)
    {
        System.out.println(getNumber(10));
    }
}