Skip to main content

Binary Search

Guess Number Higher or Lower Solution In C++/Java/Python/JS

guess-number-higher-or-lower-Problem Description
guess-number-higher-or-lower-Problem Description

Problem Description:

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 will tell you whether the number I picked is higher or lower than your guess.

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

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

Return the number that I picked.

Examples:

Input: n = 10, pick = 6
Output: 6
Explanation: You are not told what pick is in the code (Here pick = 6). You need to guess 6 using the guess API and return it.

Input: n = 1, pick = 1
Output: 1
Explanation: You are not told what pick is in the code (Here pick = 1). You need to guess 1 using guess API and return it

Input: n = 2, pick = 1
Output: 1
Explanation: You are not told what pick is in the code (Here pick = 1). You need to guess 1 using guess API and return it

Constraints:

  • 1 <= n <= 231 - 1
  • 1 <= pick <= n

Guess Number Higher or Lower Problem

In this problem, you will be interacting with a system that provides a predefined guess function. This function takes a number as input and returns -1 if the guessed number is bigger, 1 if its smaller, and 0 if it's correct. For now, just focus on the fact that the function returns 0 when the guess matches the target number. What insight can you draw from this?

Brute Force Approach

Intuition:

We have a defined range from 1 to n. A straightforward approach is to check each number one by one to see if it matches the picked number. This can be easily done using the guess function, which returns 0 when the guessed number is correct.

💡
Try it Yourself!

Guess Number Higher or Lower solution

To implement this, we iterate from 1 to n, calling the guess function for each number. If the function returns 0, we store that number as our answer and break out of the loop since there is no need to check further. Finally, we return the stored value as the correct guess.

Guess Number Higher or Lower example

Let's assume:
n: 10 pick: 7 (hardcoded in the guess function)

The program will iterate through numbers 1 to 10, calling the guess function for each number.

  • When it calls guess(1), the function returns -1 (too low).
  • When it calls guess(2), the function returns -1 (too low).
  • This continues for guess(3) , guess(4) , guess(5) , and guess(6) where all return -1 (too low).
  • When it calls guess(7), the function returns O (correct guess). The program stores 7 as the answer and exits the loop.

Dry run

Input: n = 15, pick = 5
Output: 5
Explanation: You are not told what pick is in the code (Here pick = 5). You need to guess 5 using guess API and return it

Initial Setup:

  • ans = 1
  • The loop runs from i = 2 to i = 15.

Iteration-wise Execution:

Iteration 1: i = 2

  • guess(2) is called.
  • Since 2 < pick (5), guess(2) returns 1 (meaning the picked number is greater).
  • The loop continues.

Iteration 2: i = 3

  • guess(3) is called.
  • Since 3 < 5, guess(3) returns 1.
  • The loop continues.

Iteration 3: i = 4

  • guess(4) is called.
  • Since 4 < 5, guess(4) returns 1.
  • The loop continues.

Iteration 4: i = 5

  • guess(5) is called.
  • Since 5 == pick, guess(5) returns 0.
  • ans = 5 is set.
  • The loop breaks as we found the answer.

Final Output:

  • The function returns 5, which is the correct picked number.

Steps to write code

Step 1: Initialize the answer:

  • Start with ans = 1, assuming the picked number could be 1 initially.

Step 2: Iterate through all numbers from 2 to n:

  • Use a for loop that runs from i = 2 to n.

Step 3: Check if the current number is the picked number:

  • Call guess(i), which returns:
    • 0 if i is the picked number (correct guess).
    • -1 if i is too high.
    • 1 if i is too low.
  • If guess(i) == 0, update ans = i and break the loop.

Step 4: Return the found number:

  • Once the correct number is found, return ans.
Guess Number Higher or Lower solution
Guess Number Higher or Lower solution in c++ 
/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is higher than the picked number
 *			      1 if num is lower than the picked number
 *               otherwise return 0
 * int guess(int num);
 */


class Solution {
public:
    // Function to find the picked number using the guess API
    int guessNumber(int n) {
        // Start the search from number 1
        int ans = 1;
        
        // Iterate over the numbers from 2 to n
        for (int i = 2; i <= n; ++i) {
            // If guess is correct, store the value of i as the answer
            if (guess(i) == 0) {
                ans = i;
                
                // Exit loop as the correct number is found
                break;
            }
        }
        
        // Return the correct guess
        return ans;
    }
};

Guess Number Higher or Lower solution in java 
/** 
* Forward declaration of guess API.
* @param  num   your guess
* @return 	     -1 if num is higher than the picked number
*			      1 if num is lower than the picked number
*               otherwise return 0
* int guess(int num);
*/

class Solution extends GuessGame {
    
    // Function to find the picked number using the guess API
    public int guessNumber(int n) {
        
        // Start the search from number 1
        int ans = 1;
        
        // Iterate over the numbers from 2 to n
        for (int i = 2; i <= n; ++i) {
            
            // If guess is correct, store the value of i as the answer
            if (guess(i) == 0) {
                ans = i;
                
                // Exit loop as the correct number is found
                break;
            }
        }
        
        // Return the correct guess
        return ans;
    }
}

Guess Number Higher or Lower solution in python 
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
#          1 if num is lower than the picked number
#          otherwise return 0
# def guess(num: int) -> int:

class Solution(GuessGame):
    def guessNumber(self, n: int) -> int:
        # Start the search from number 1
        ans = 1

        # Iterate over the numbers from 2 to n
        for i in range(2, n + 1):
            # If guess is correct, store the value of i as the answer
            if self.guess(i) == 0:
                ans = i

                # Exit loop as the correct number is found
                break

        # Return the correct guess
        return ans

Guess Number Higher or Lower solution in javascript 
/** 
 * Forward declaration of guess API.
 * @param {number} num   your guess
 * @return     -1 if num is higher than the picked number
 *              1 if num is lower than the picked number
 *              otherwise return 0
 * var guess = function(num) {}
 */


/**
 * @param {number} n
 * @return {number}
 */
var guessNumber = function(n) {
    // Start by assuming the number is 1
    let ans = 1;

    // Loop through the numbers from 2 to n
    for (let i = 2; i <= n; ++i) {
        // Use the guess API to check the guess
        if (guess(i) === 0) {
            // If the guess is correct, update the answer and break
            ans = i;
            break;
        }
    }

    // Return the found number
    return ans;
};

Complexity Analysis of the problem

Time Complexity: O(n)

Initialization:

  • Setting ans = 1 takes O(1) time.

For Loop Execution:

  • The loop runs from i = 2 to i = n.
  • In the worst case, it will iterate (n - 1) times if the picked number is n.
  • Each iteration makes one call to guess(i), which also takes O(1) time.

Condition Check:

  • In each iteration, the if condition guess(i) == 0 is checked.
  • This check is performed (n - 1) times in the worst case, each taking O(1) time.

Updating and Breaking:

  • When guess(i) == 0 is true, it sets ans = i and breaks out of the loop.
  • These operations are O(1) and happen only once.

Return Statement:

  • Returning the value of ans takes O(1) time.

Overall Complexity:

  • The dominant factor here is the for loop, which can run up to n - 1 times.
  • Therefore, the total time complexity is O(n).

Space Complexity: O(1)

Auxiliary Space Complexity
Auxiliary space refers to extra space used by the algorithm that is not part of the input or output.

  • In this code: Auxiliary Space Complexity = O(1)
    • We use only one integer variable ans, which takes O(1) space.
    • The loop and function calls do not use any additional data structures.
    • The function does not use recursion, so no extra call stack space is used.

Total Space Complexity
Total space complexity includes both the auxiliary space and the input space.

  • In this code: Total Space Complexity = O(1)
    • The input parameter n is given and stored in memory, but it is not created within the function.
    • No additional arrays, lists, or complex data structures are used.

Hence, the overall space complexity of the code is O(1)

Is the brute force approach efficient?

The brute force approach has a time complexity of O(n). Since n can go up to 2³¹ - 1 (which is 2,147,483,647), this means the worst case would require billions of iterations.

The system can process at most 106 operations per second, meaning any approach exceeding this limit will be too slow. If the problem requires significantly more operations, brute force becomes infeasible.

But notice that we haven’t used the fact that the guess function also returns -1 or 1. Can we use this extra information to find a more efficient solution?

Optimal Approach

Intuition:

We have a defined range from 1 to n. Any number between 1 and n, including them, could be the system-picked number as the problem is interactive. Now, to optimize the solution, we can see that O(n) didn't work, so we need to do better than O(n). This gives a hint that we can't check for every number from 1 t0 n. We have to strategically choose a set of numbers from 1 to n where we can find our answer.

Let's start by choosing any number between 1 and n. Let's assume the number is i. This means that the picked number will either be i itself, or it will lie further to the left of i or the right of i. If we use the guess function on this i. We will get one of the three values -1, 0, 1.

What conclusions can we make from this?

According to the result of the guess function, we can make the following decisions:

  • If guess(i) == 0, we found the correct number!
  • If guess(i) == -1, our guess i is too high, so the correct number must be somewhere to the left (smaller than i).
  • If guess(i) == 1, our guess i is too low, meaning the correct number is somewhere to the right (greater than i).
💡
Try it Yourself!

This means that if i is not the correct number, we immediately know which side to search next, either left or right. As a result, we can ignore the other half of the numbers, significantly reducing the number of guesses needed to find the correct answer.

Guess Number Higher or Lower example:

guess-number-higher-or-lower

Let's take an example where we have an array of numbers from 1 to 50, and the system has picked the number 23.

We start by choosing a number in the middle, say i = 25.

  • Since 25 is greater than 23, the guess(25) function returns -1.
  • This means the correct number is somewhere to the left, so we ignore all numbers greater than 25 and look in the smaller half.

Next, we choose i = 15.

  • Since 15 is less than 23, the guess(15) function returns 1.
  • This means the correct number is somewhere to the right, so we ignore all numbers less than 15 and focus on the larger half.

To efficiently search for the correct number, we start by defining our search space using two pointers: low, which starts at 1, and high, which starts at n. These pointers represent the range in which the correct number could be found.

Next, instead of checking every number one by one, we choose a number in the middle of our current search space. This middle number helps us divide the range into two halves, making our search more efficient.

We then use the guess function to check whether the chosen number is correct. If it matches the picked number, we return it. Otherwise, the function tells us if our guess is too high or too low. If the guess is too high, it means the correct number must be on the left side, so we update the high to narrow the search. If the guess is too low, the correct number must be on the right side, so we update the low.

By repeating this process, we keep shrinking the search space until we find the correct number. This method of continuously dividing the range in half is known as Binary Search, allowing us to find the answer much faster than checking every number individually.

To know more about binary search and its uses you can refer to the following article.

Let us understand this with a video,

0:00
/2:24

guess-number-higher-or-lower-Optimal Approach Explaination

💡
binary search in detail !!

Dry run

Input: n = 15, pick = 5
Output: 5
Explanation: You are not told what pick is in the code (Here pick = 5). You need to guess 5 using guess API and return it.

Initial Setup:

  • n = 15
  • low = 1, high = 15
  • The picked number is 5.

Iteration 1:

  • low = 1, high = 15
  • Calculate mid = low + (high - low) / 2 = 1 + (15 - 1) / 2 = 1 + 14 / 2 = 1 + 7 = 8.
  • Check guess(8):
    • Since guess(8) will return -1 (as 8 is greater than the picked number 5), we update high = mid - 1 = 8 - 1 = 7.
  • Updated values: low = 1, high = 7

Iteration 2:

  • low = 1, high = 7
  • Calculate mid = low + (high - low) / 2 = 1 + (7 - 1) / 2 = 1 + 6 / 2 = 1 + 3 = 4.
  • Check guess(4):
    • Since guess(4) will return 1 (as 4 is less than the picked number 5), we update low = mid + 1 = 4 + 1 = 5.
  • Updated values: low = 5, high = 7

Iteration 3:

  • low = 5, high = 7
  • Calculate mid = low + (high - low) / 2 = 5 + (7 - 5) / 2 = 5 + 2 / 2 = 5 + 1 = 6.
  • Check guess(6):
    • Since guess(6) will return -1 (as 6 is greater than the picked number 5), we update high = mid - 1 = 6 - 1 = 5.
  • Updated values: low = 5, high = 5

Iteration 4:

  • low = 5, high = 5
  • Calculate mid = low + (high - low) / 2 = 5 + (5 - 5) / 2 = 5 + 0 / 2 = 5.
  • Check guess(5):
    • Since guess(5) will return 0 (as 5 is the picked number), we return 5.

Final Output:

  • The function successfully finds the picked number 5.

Steps to write code

Step 1: Initialize Low and High Pointers

  • Start by defining two pointers, low and high.
  • low is set to 1 (the starting point of the range).
  • high is set to n (the upper limit of the range).

This represents the range [low, high] where the picked number can be located.


Step 2: Set Up a Loop for Binary Search

  • Use a while loop that continues as long as low <= high.
  • This ensures that the search space continues to shrink until the correct number is found.

Step 3: Calculate the Middle Index

  • Within the loop, calculate the middle index mid of the current range [low, high].
  • The formula low + (high - low) / 2 is used to prevent overflow that could happen if you simply used (low + high) / 2.

Step 4: Make a Guess at the Middle Index

  • Call the guess(mid) function to compare the middle value to the picked number.
    • If guess(mid) == 0, it means the picked number is mid. You return mid as the correct answer.
    • If guess(mid) == 1, it means the picked number is greater than `mid, so you need to search the right half. You adjust low to mid + 1.
    • If guess(mid) == -1, it means the picked number is smaller than mid, so you need to search the left half. You adjust high to mid - 1.

Step 5: Return the Correct Answer

  • If the picked number is found inside the loop (when guess(mid) == 0), return the number immediately.
  • If the loop ends without finding the correct number (which shouldn't happen in this problem setup), return -1 as a fallback. The code won't reach here.
Guess Number Higher or Lower leetcode solution
Guess Number Higher or Lower solution in c++ 
/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is higher than the picked number
 *			      1 if num is lower than the picked number
 *               otherwise return 0
 * int guess(int num);
 */


class Solution {
public:
    // Step 1: Initialize low and high to define the search space
    int guessNumber(int n) {
        int low = 1, high = n;
        
        // Step 2: Perform binary search while low is less than or equal to high
        while (low <= high) {
            // Step 3: Calculate the middle index to reduce the search space
            int mid = low + (high - low) / 2;
            
            // Step 4: Check if mid is the picked number
            if (guess(mid) == 0) {
                return mid;  // Correct guess, return the number
            }
            // Step 5: If guess is too low, adjust the search space to the right half
            else if (guess(mid) == 1) {
                low = mid + 1;
            }
            // Step 6: If guess is too high, adjust the search space to the left half
            else {
                high = mid - 1;
            }
        }
        
        // Step 7: Return -1 if no number is found (not applicable here)
        return -1;
    }
};

Guess Number Higher or Lower solution in java 
/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is higher than the picked number
 *			      1 if num is lower than the picked number
 *               otherwise return 0
 * int guess(int num);
 */

class Solution extends GuessGame {
    // Step 1: Initialize low and high to define the search space
    public int guessNumber(int n) {
        int low = 1, high = n;
        
        // Step 2: Perform binary search while low is less than or equal to high
        while (low <= high) {
            // Step 3: Calculate the middle index to reduce the search space
            int mid = low + (high - low) / 2;
            
            // Step 4: Check if mid is the picked number
            if (guess(mid) == 0) {
                return mid;  // Correct guess, return the number
            }
            // Step 5: If guess is too low, adjust the search space to the right half
            else if (guess(mid) == 1) {
                low = mid + 1;
            }
            // Step 6: If guess is too high, adjust the search space to the left half
            else {
                high = mid - 1;
            }
        }
        
        // Step 7: Return -1 if no number is found (not applicable here)
        return -1;
    }
}

Guess Number Higher or Lower solution in python 
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
#          1 if num is lower than the picked number
#          otherwise return 0
# def guess(num: int) -> int:

class Solution(GuessGame):
    def guessNumber(self, n: int) -> int:
        # Step 1: Initialize low and high to define the search space
        low, high = 1, n
        
        # Step 2: Perform binary search while low is less than or equal to high
        while low <= high:
            # Step 3: Calculate the middle index to reduce the search space
            mid = low + (high - low) // 2
            
            # Step 4: Check if mid is the picked number
            if self.guess(mid) == 0:
                return mid  # Correct guess, return the number
            # Step 5: If guess is too low, adjust the search space to the right half
            elif self.guess(mid) == 1:
                low = mid + 1
            # Step 6: If guess is too high, adjust the search space to the left half
            else:
                high = mid - 1
        
        # Step 7: Return -1 if no number is found (not applicable here)
        return -1

Guess Number Higher or Lower solution in javascript 
/** 
 * Forward declaration of guess API.
 * @param {number} num   your guess
 * @return     -1 if num is higher than the picked number
 *              1 if num is lower than the picked number
 *              otherwise return 0
 * var guess = function(num) {}
 */


/**
 * @param {number} n
 * @return {number}
 */
var guessNumber = function(n) {
    // Step 1: Initialize low and high to define the search space
    let low = 1, high = n;
    
    // Step 2: Perform binary search while low is less than or equal to high
    while (low <= high) {
        // Step 3: Calculate the middle index to reduce the search space
        let mid = low + Math.floor((high - low) / 2);
        
        // Step 4: Check if mid is the picked number
        if (guess(mid) === 0) {
            return mid;  // Correct guess, return the number
        }
        // Step 5: If guess is too low, adjust the search space to the right half
        else if (guess(mid) === 1) {
            low = mid + 1;
        }
        // Step 6: If guess is too high, adjust the search space to the left half
        else {
            high = mid - 1;
        }
    }
    
    // Step 7: Return -1 if no number is found (not applicable here)
    return -1;
};

Complexity Analysis of the problem

Time Complexity: O(log n)

While Loop:

  • In each iteration of the while loop, we are halving the search space by adjusting either the low or high pointer based on the result of the guess(mid) function.
  • Initially, the search space is the entire range from 1 to n (i.e., n numbers).
  • After the first iteration, the search space is reduced to half, then a quarter, and so on.
    n → n/2 → n/4 → n/8 → ... → 1
  • The number of iterations required to reduce the search space to a single number is proportional to the logarithm of the total number of elements, i.e., log₂(n).

Complexity of each iteration:

  • In each iteration, we perform a constant amount of work:
    • Calculating the middle value (mid),
    • Calling the guess(mid) function, and
    • Adjusting the low or high pointer based on the result.
  • Each of these steps takes constant time, so the time for each iteration is O(1).

Overall Time Complexity:

  • Since the loop runs for log₂(n) iterations and each iteration takes constant time, the overall time complexity is O(log n).

Space Complexity: O(1)

Auxiliary Space Complexity:
It refers to the extra space or temporary space used by the algorithm apart from the input.

  • In this solution, the only extra space used is the variables low, high, and mid, which are used to keep track of the search space during the binary search.
  • These variables take up constant space, and no additional data structures (like arrays, lists, or trees) are used.

Therefore, the auxiliary space complexity is O(1).

Total Space Complexity:
It includes both the space used by the algorithm itself (auxiliary space) and the input space.

  • The input space here is represented by the integer n, which is a single value and does not consume extra space that scales with the problem size (i.e., there is no array or data structure holding multiple elements).

Thus, the total space complexity is the same as the auxiliary space complexity, which is O(1).

Similar Problems

Now we have successfully tackled this problem, let's try these similar problems:-

1. Guess Number Higher or Lower II

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

  1. I pick a number between 1 and n.
  2. You guess a number.
  3. If you guess the right number, you win the game.
  4. 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.
  5. 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.

2. First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

3. Find K Closest Elements

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

  • |a - x| < |b - x|, or
  • |a - x| == |b - x| and a < b