Problem Description
Welcome to another fun coding challenge! Today, we'll be tackling the Guess Number Higher or Lower problem.
You are playing the Guess Game with your friend. In this game, your friend thinks of a number between 1 and n, and you have to guess which number they have chosen. Each time you guess a number, your friend will tell you whether the number is higher, lower, or equal to their chosen number. You call a pre-defined API guess(int num) which returns 3 possible results:
-1: The number I guessed is higher than the number your friend has chosen.
1: The number I guessed is lower than the number your friend has chosen.
0: Congratulations! You've guessed the correct number!
That's it! Now, let's dive into the solution.
Solution
We can use a binary search approach to solve this problem. Since the numbers are sorted in ascending order, we can compare the middle element of the range with the target number. Based on the result of the guess() function, we can either narrow down the search to the lower half or the upper half of the range.
Here's the Python code for our solution:
def guessNumber(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
Let's go through this code step-by-step.
- We initialize two pointers
left and right to the beginning and end of the range, respectively.
left, right = 1, n
- We use a
while loop to repeatedly divide the range in half and narrow down the search space.
while left <= right:
Note that we're using <= instead of < in the loop condition. This is because we want to continue the loop until the range is of size 1 (i.e., left == right), which may be the target number.
- We calculate the middle index of the current search space.
mid = (left + right) // 2
- We call the
guess() function with the middle element of the range and store the result.
result = guess(mid)
- Based on the result of the
guess() function, we either narrow down the search to the lower half or the upper half of the range.
if result == 0:
return mid
elif result == -1:
right = mid - 1
else:
left = mid + 1
If result == 0, then we know that we've guessed the correct number, so we return mid. If result == -1, then we know that the target number is in the lower half of the range, so we set right = mid - 1. Otherwise, we know that the target number is in the upper half of the range, so we set left = mid + 1.
Complexity Analysis
Now that we have our solution, let's analyze its time and space complexity.
Time Complexity
Our solution uses binary search to guess the target number. Since we're dividing the search space in half at each step, the time complexity of our solution is O(log n), where n is the size of the range.
Space Complexity
Our solution uses a constant amount of extra space to keep track of the pointers left, right, and mid, as well as the result of the guess() function. Therefore, the space complexity of our solution is O(1).
Conclusion
And there you have it! We've successfully tackled the Guess Number Higher or Lower problem. I hope you found this blog post helpful and informative. Happy Coding! 😎
