Domain 1EasyCORE

Guess Number Higher or Lower

We are playing a guessing game where I pick a number from 1 to n, and you have to guess which number it is. After each incorrect guess, I will tell you whether the number I picked is higher or lower than your guess. The goal is to return the number that was picked.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Binary Search

374. Guess Number Higher or Lower

Model: qwen2.5-coder:14b
Topics: Binary Search
FAANG asked: 1
Acceptance rate: 45.1%


Problem Breakdown

We are playing a guessing game where I pick a number from 1 to n, and you have to guess which number it is. After each incorrect guess, I will tell you whether the number I picked is higher or lower than your guess. The goal is to return the number that was picked.

Inputs:

  • An integer n representing the upper bound of the range from which the number is picked.
  • A hidden integer pick (the number I picked) within the range [1, n].

Outputs:

  • The integer pick that was chosen.

Implicit Constraints or Tricky Edge Cases:

  • The range can be as large as 2^31 - 1, so we need to consider potential overflow issues.
  • The number could be at either end of the range (1 or n), which might affect our initial guesses.

Intuition

The brute-force approach would involve guessing every number from 1 to n until the correct one is found. This method has a time complexity of O(n) and is inefficient, especially for large values of n.

A better approach is to use binary search, which leverages the fact that we can eliminate half of the remaining possibilities with each guess. By starting in the middle of the range and adjusting our guesses based on whether the hidden number is higher or lower, we can significantly reduce the number of guesses needed.

Approach

We will use a binary search algorithm to efficiently find the hidden number:

  1. Initialize two pointers: left set to 1 (the start of the range) and right set to n (the end of the range).
  2. While left is less than or equal to right:
    • Calculate the middle point mid as (left + right) // 2.
    • Use the guess(mid) API to determine if the hidden number is higher, lower, or equal to mid.
    • If guess(mid) returns 0, we have found the correct number and can return mid.
    • If guess(mid) returns -1, it means the hidden number is lower than mid, so we adjust our search range by setting right to mid - 1.
    • If guess(mid) returns 1, it means the hidden number is higher than mid, so we adjust our search range by setting left to mid + 1.

Complexity Analysis

  • Time Complexity: O(log n) because each guess halves the search space.
  • Space Complexity: O(1) since we are using a constant amount of extra space.

Solution

# 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: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:
        left, right = 1, n
        
        while left <= right:
            mid = (left + right) // 2
            result = guess(mid)
            
            if result == 0:
                return mid
            elif result == -1:
                right = mid - 1
            else:
                left = mid + 1

Edge Cases Handled

  • Edge Case: When n is 1, the only possible number to guess is 1.
  • Edge Case: When the hidden number is at the boundary (either 1 or n), the binary search will correctly adjust the range until it finds the number.
  • Edge Case: Large values of n are handled efficiently by the binary search approach, which reduces the number of guesses logarithmically.