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
nrepresenting 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
pickthat 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:
- Initialize two pointers:
leftset to 1 (the start of the range) andrightset to n (the end of the range). - While
leftis less than or equal toright:- Calculate the middle point
midas(left + right) // 2. - Use the
guess(mid)API to determine if the hidden number is higher, lower, or equal tomid. - If
guess(mid)returns 0, we have found the correct number and can returnmid. - If
guess(mid)returns -1, it means the hidden number is lower thanmid, so we adjust our search range by settingrighttomid - 1. - If
guess(mid)returns 1, it means the hidden number is higher thanmid, so we adjust our search range by settinglefttomid + 1.
- Calculate the middle point
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
nis 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
nare handled efficiently by the binary search approach, which reduces the number of guesses logarithmically.