374. Guess Number Higher or Lower

Hello, reader 👋🏽 ! Welcome to day 46 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 374. Guess Number Higher or Lower.

🤔 Problem Statement

• There's a guessing game where a random number is picked from 1 to n and that has to be guessed.
• A predefined API int guess(int num) is used which tells whether the number picked is higher or lower than the guess.

• The API returns three possible values:

  • -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 was picked.

💬 Thought Process - Binary Search

• The number picked is in the range 1 to n and those numbers are sorted.
• Hence, we can apply binary search and reduce our search space to one-half and keep guessing a number.
• Our initial search space would be from 1 to n, and we shall apply binary search to figure out if the number picked was less than, equal to or greater than the middle number.
• If it was less than the mid, we will continue searching in the left half [1,mid-1].
• If it was equal to mid, we will return the middle number.

• If it was greater than the mid, we will continue searching the right half [mid+1, n].

• This will be repeated until we find the number.

👩🏽‍💻 Solution - Binary Search

• Below is the code for the binary search approach.

  public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int start = 1, end = n;
        while(start <= end) {
            int mid = start + (end - start)/2;
            int result = guess(mid);
  
            if(result == 0) return mid;
            if(result == -1)  {
                end = mid-1;
            }
            else {
                start = mid+1;
            }
        }
  
        return -1;
    }
  }
  

  Time Complexity: O(log n)
    - n = the maximum number
  Space Complexity: O(1)
  

You can find the link to the GitHub repo for this question here: 374. Guess Number Higher or Lower.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!