Tuesday, October 12, 2021

[LeetCode] Guess Number Higher or Lower

Problem: 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 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.

Example:

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

Approach: It's a straight forward binary search problem. You can look at the implementation to understand the approach.


Implementation in C#:

        public int GuessNumber(int n)

    {
        int start = 0, end = n;
        while (start <=  end)
        {
            int mid = start + (end - start) / 2;
            int guessRes = guess(mid);
            if (guessRes == 0)
            {
                return mid;
            }
            else if(guessRes == -1)
            {
                end = mid - 1;
            }
            else
            {
                start = mid + 1;
            }
        }
        return -1;
    }


Complexity: O(logn)

No comments:

Post a Comment