Question

Formatted question description: https://leetcode.ca/all/374.html

 374	Guess 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'll tell you whether the number is higher or lower.

 You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

 -1 : My number is lower
 1 : My number is higher
 0 : Congrats! You got it!

 Example :

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

Algorithm

Binary search.

Code

Java

  • 
    public class Guess_Number_Higher_or_Lower {
    
    
        public class Solution extends GuessGame {
            public int guessNumber(int n) {
                int low = 1;
                int high = n;
                while (low <= high) {
                    int mid = low + (high - low) / 2;
                    int res = guess(mid);
                    if (res == 0)
                        return mid;
                    else if (res < 0)
                        high = mid - 1;
                    else
                        low = mid + 1;
                }
                return -1;
            }
        }
    }
    
    // stub
    class GuessGame {
        public int guess(int i) {
            return 0;
        }
    }
    
  • // OJ: https://leetcode.com/problems/guess-number-higher-or-lower/
    // Time: O(logN)
    // Space: O(1)
    class Solution {
    public:
        int guessNumber(int n) {
            int L = 1, R = n;
            while (L <= R) {
                int M = L + (R - L) / 2, g = guess(M);
                if (g == 0) return M;
                if (g == 1) L = M + 1;
                else R = M - 1;
            }
            return -1;
        }
    };
    
  • # The guess API is already defined for you.
    # @param num, your guess
    # @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
    # def guess(num):
    
    class Solution(object):
      def guessNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        l, r = 1, n
        while l < r:
          m = l + (r - l) / 2
          g = guess(m)
          if g == -1:
            r = m - 1
          elif g == 1:
            l = m + 1
          else:
            return m
        return l
    
    

All Problems

All Solutions