algoadvance

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 predefined API guess(int num) which returns 3 possible results:

Implement a function int guessNumber(int n) that uses the guess API to find the number I picked.

Clarifying Questions

  1. What are the constraints on n?
    • 1 <= n <= 2^31 - 1.
  2. Do we need to handle invalid inputs or out-of-bound values?
    • We can assume the function will be called with valid inputs within the given range for n.

Strategy

To find the number that the system has picked, we can use a binary search algorithm. Since the feedback from the guess API tells us whether the number is higher or lower, binary search is efficient and appropriate for this problem.

  1. Initialize the search bounds with left = 1 and right = n.
  2. Use a loop to repeatedly narrow down the search range:
    • Calculate the middle point mid = left + (right - left) // 2.
    • Call the guess(mid) function.
    • Depending on the result:
      • If it returns 0, then mid is the correct guess.
      • If it returns -1, the picked number is lower than mid, so adjust the search range to left to mid - 1.
      • If it returns 1, the picked number is higher than mid, so adjust the search range to mid + 1 to right.
  3. Continue the above steps until the correct number is found.

Code

Here’s the implementation of the solution:

def guessNumber(n: int) -> int:
    left, right = 1, n
    
    while left <= right:
        mid = left + (right - left) // 2
        res = guess(mid)
        
        if res == 0:
            return mid
        elif res == -1:
            right = mid - 1
        else:
            left = mid + 1
    
    return -1  # This line is just for completeness; the loop should always return within the loop.

## Time Complexity
The time complexity of this solution is O(log n) since we are effectively dividing the search space in half with each iteration of the binary search.

Note: Since the `guess` function is predefined, ensure it's available in the environment where you test this solution or mock it for testing purposes.

Try our interview co-pilot at AlgoAdvance.com