We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Guess Number Higher or Lower

Difficulty: Easy

Problem Description

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 if your guess is higher, 1 if your guess is lower, and 0 if your guess is correct. Your task is to return the number that I picked.

Key Insights

  • The problem requires a strategy to efficiently guess a number within a limited range.
  • A binary search approach minimizes the number of guesses by halving the search space with each guess.
  • The interactive nature of the problem means we must adjust our guess based on feedback from each attempt.

Space and Time Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Solution

The solution utilizes a binary search algorithm to efficiently narrow down the possible number choices. We initialize two pointers, low and high, representing the current search range. In each iteration, we calculate the midpoint and use the guess function to get feedback. Based on the feedback, we adjust our search range: if the guess was too high, we move the high pointer down; if it was too low, we move the low pointer up. This process continues until we find the correct number.

Code Solutions

def guessNumber(n: int) -> int:
    low, high = 1, n
    while low <= high:
        mid = low + (high - low) // 2
        result = guess(mid)
        if result == 0:
            return mid
        elif result == -1:
            high = mid - 1
        else:
            low = mid + 1
← Back to All Questions