374. Guess Number Higher or Lower

 374Guess 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 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 1:

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

Example 2:

Input: n = 1, pick = 1
Output: 1

Example 3:

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

Example 4:

Input: n = 2, pick = 2
Output: 2

 

Constraints:

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



                                                                                                         

Solution To the Above Question

This question is similar to the binary search and if you know binary search then you can easily solve this.
Just read the binary search algo once and then you can easily solve this.

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return       -1 if num is lower than the guess number
 *                1 if num is higher than the guess number
 *               otherwise return 0
 * int guess(int num);
 */

class Solution {
public:

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

Post a Comment

0 Comments