Guess Number Higher or Lower LeetCode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple GoogleViews 4497

Problem Statement

Guess Number Higher or Lower LeetCode Solution – 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.

Example:

Test Case 1:

Input:

n = 10

pick = 2

Output:

2

Test Case 2:

Input:

n = 6

pick = 4

Output:

4

Explanation for Guess Number Higher or Lower LeetCode Solution :

i) For the first test case, we chose 2 so the output is  2.

ii) For the second test case, we chose 4 so the output is  4.

Approach

Idea:

Here the linear solution is pretty obvious. We can iterate from 1 to n and check for every number if it’s matching the pick. But it will take linear time. The time complexity will be O(n).

So the question is how can we optimize the time complexity? Here the input is in sorted order and for every guess, we have 3 options. Either it’s the same. If it’s the same we can return the number. If it’s less than the picked number, we need to search it in the range [number+1…n]. If it’s greater than the picked number, we need to search it in the range [number-1…n]. Here for every guess, we are reducing the input by half. So the time complexity will be O(log2​n). Basically, we can apply Binary Search here.

Let’s see the first test case:

start  end  pick  guess(pick)

1           10     5         -1

1           4       2          0   (we got our number)

Code

Java Program for Guess Number Higher or Lower LeetCode Solution

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

C++ Program for Guess Number Higher or Lower LeetCode Solution

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

Complexity Analysis for Guess Number Higher or Lower LeetCode Solution

Time Complexity

Here for every guess, we are reducing our search portion by half. So the time complexity is O(log2​n).

Space Complexity

Here we are not using any extra space. So space complexity is O(1).

Reference: https://en.wikipedia.org/wiki/Binary_search_algorithm

Translate »