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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Guess Number Higher or Lower

Number: 374

Difficulty: Easy

Paid? No

Companies: Meta, Bloomberg, Amazon, Google

Problem Description

We need to guess the number picked by the system (via the guess API) from the range 1 to n. The API returns whether our guess is higher, lower, or exactly the pick. Our task is to find the correct number.

Key Insights

  • The problem can be effectively solved using binary search since the search space is sorted by nature (1 to n).
  • Each API call helps to halve the search space, leading to an efficient solution.
  • Be cautious with potential overflow when calculating the mid-point by using low + (high - low) // 2.

Space and Time Complexity

Time Complexity: O(log n) since we binary search the range. Space Complexity: O(1) as we use a constant amount of extra space.

Solution

We use a binary search algorithm to efficiently locate the target number. We initialize two pointers: low (1) and high (n). In each iteration, we compute the mid-point, then call the guess API. Based on the response:

  • If guess(mid) returns 0, we have found the number.
  • If it returns -1, it indicates that our guess is higher than the pick, so we update the high pointer to mid - 1.
  • If it returns 1, it indicates that our guess is lower than the pick, so we update the low pointer to mid + 1. This approach guarantees a logarithmic time solution.

Code Solutions

# Python solution using binary search
class Solution:
    def guessNumber(self, n: int) -> int:
        # Initialize low and high pointers
        low, high = 1, n
        # Continue binary search until low exceeds high
        while low <= high:
            # Calculate midpoint safely to prevent overflow
            mid = low + (high - low) // 2
            # Call the guess API with mid
            result = guess(mid)
            # If the guess is correct, return mid
            if result == 0:
                return mid
            # If guess was too high, adjust the high pointer
            elif result == -1:
                high = mid - 1
            # If guess was too low, adjust the low pointer
            else:
                low = mid + 1
        # Return low (ideally should never reach here if pick exists in [1, n])
        return low
← Back to All Questions