{x}
blog image

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 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 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

 

Constraints:

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

374. Guess Number Higher or Lower

This problem requires you to guess a number between 1 and n using a guess(num) API. The API returns:

  • -1: Your guess is too high.
  • 1: Your guess is too low.
  • 0: Your guess is correct.

The optimal solution uses binary search. Binary search is efficient because it repeatedly divides the search interval in half.

Approach

  1. Initialization: Set left to 1 and right to n. These variables define the search space.

  2. Iteration: While left is less than right:

    • Calculate the middle value mid using (left + right) / 2 (or, even better, (left + right) >>> 1 in Java or similar bitwise operations in other languages to avoid potential integer overflow).
    • Call guess(mid).
    • If guess(mid) is:
      • <= 0: The guessed number is either correct or too high. Update right to mid.
      • > 0: The guessed number is too low. Update left to mid + 1.

  3. Result: After the loop, left and right will converge to the correct number. Return left.

Time and Space Complexity

  • Time Complexity: O(log n). Binary search halves the search space with each guess.
  • Space Complexity: O(1). Constant extra space is used.

Code in Multiple Languages

Python

def guessNumber(n: int) -> int:
    left, right = 1, n
    while left < right:
        mid = (left + right) // 2  # Integer division
        if guess(mid) <= 0:
            right = mid
        else:
            left = mid + 1
    return left

Java

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 1, right = n;
        while (left < right) {
            int mid = (left + right) >>> 1; // Bitwise right shift for efficiency
            if (guess(mid) <= 0) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

C++

int guessNumber(int n) {
    int left = 1, right = n;
    while (left < right) {
        int mid = left + (right - left) / 2; // Avoid potential overflow
        if (guess(mid) <= 0) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
var guessNumber = function(n) {
    let left = 1, right = n;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (guess(mid) <= 0) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
};

Go

func guessNumber(n int) int {
    left, right := 1, n
    for left < right {
        mid := (left + right) / 2
        if guess(mid) <= 0 {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

Note: The guess() function is assumed to be pre-defined and available in the code environment. The provided solutions demonstrate the core binary search algorithm to solve the problem. Remember to adapt the code based on your specific platform and constraints.