Solution For Guess Number Higher Or Lower

Problem statement:

You are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number is higher or lower.

You call a pre-defined API int guess(int num), which returns 3 possible results:

-1: The number I picked is lower than your guess (i.e. pick < num).
1: The number I picked is higher than your guess (i.e. pick > num).
0: The number I picked is equal to your guess (i.e. pick == num).

Return the number that I picked.

Solution:

The given problem can be solved using binary search. The basic idea is to find the mid-point of the search space and to determine whether to search in the left or the right part of the space based on the guess result. The search space will keep getting smaller with each guess until the number is found.

For the implementation, we will maintain two pointers, left and right, which will represent the start and end of the search space, respectively. We will then calculate the mid-point of the search space as (left+right)/2. We will then call the guess API with this mid-point and check its result. Depending on the result, we will either move the left pointer to mid+1 or the right pointer to mid-1. We will repeat this process until we find the number.

Here is the implementation:

public int guessNumber(int n) {
int left = 1;
int right = n;
while (left <= right) {
int mid = left + (right - left) / 2;
int result = guess(mid);
if (result == 0) {
return mid;
} else if (result == 1) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Number not found
}

In the above implementation, we start by setting the left pointer to 1 and the right pointer to n, which represents the initial search space. We then enter a while loop and calculate the mid-point using the formula (left+right)/2. We then call the guess API with this mid-point and check its result. If the result is 0, we have found the number and we return it. If the result is 1, we set the left pointer to mid+1, which means we need to search in the right part of the search space. If the result is -1, we set the right pointer to mid-1, which means we need to search in the left part of the search space. We then repeat this process until we find the number.

Time Complexity: O(log n), where n is the size of the search space.

Space Complexity: O(1), as we are not using any extra space apart from the two pointers.

Step by Step Implementation For Guess Number Higher Or Lower

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

-1 : My number is lower
 1 : My number is higher
 0 : Congrats! You got it!
Example :

Input: n = 10, pick = 6
Output: 6

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num):

class Solution(object):
    def guessNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        left = 1
        right = n
        while left <= right:
            mid = left + (right - left) // 2
            if guess(mid) == 0:
                return mid
            elif guess(mid) == 1:
                left = mid + 1
            else:
                right = mid - 1
        return -1

var guessNumber = function(n) {
    // we use a binary search algorithm to find the number
    // set left and right bounds
    let left = 1;
    let right = n;
    
    // while the left bound is less than the right bound
    while (left <= right) {
        // find the middle number
        let middle = Math.floor((left + right) / 2);
        // if the guess is correct, return the number
        if (guess(middle) === 0) {
            return middle;
        // if the guess is too low, set the left bound to be one more than the middle
        } else if (guess(middle) === -1) {
            left = middle + 1;
        // if the guess is too high, set the right bound to be one less than the middle    
        } else {
            right = middle - 1;
        }
    }
};

#include 

using namespace std;

// Simple Binary Search
// Time Complexity: O(log n)
// Space Complexity: O(1)

int guessNumber(int n) {
    int left = 1, right = n;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int res = guess(mid);
        if (res == 0) {
            return mid;
        } else if (res < 0) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Example:

n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

class Solution {
    public int GetMoneyAmount(int n) {
        
    }
}