algoadvance

Leetcode 374. Guess Number Higher or Lower

Problem Statement

The “Guess Number Higher or Lower” is a classic problem in computer algorithms. Here is the formal problem statement:

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 3 possible results:

• -1: Your guess is higher than the number I picked.
• 1: Your guess is lower than the number I picked.
• 0: Your guess is equal to the number I picked.

Your goal is to find the number I picked.

Clarifying Questions

1. Range of n: What is the typical value range of n? Although the general approach wouldn’t change, the value of n might impact the efficiency details.
2. Number of guesses: Is there a constraint on the maximum number of guesses allowed?
3. Thread Safety: Is the environment multi-threaded, or can we assume single-threaded execution?
4. Return Value: Should our function return the picked number when guessed correctly, or handle the result differently?

Given common conventions and based on the problem statement, we can assume:

• n can be any value within the typical bounds of an integer.
• The function returns the guessed number.

Strategy

To solve this problem efficiently, a binary search algorithm is appropriate, leveraging the feedback provided by the guess(int num) API. Here’s the plan:

1. Initialize two pointers, low and high, to 1 and n, respectively.
2. Perform a binary search:
   • Calculate the middle point: mid = low + (high - low) / 2.
   • Call the guess(mid) API with the middle point.
   • If guess(mid) returns 0, we have found the number.
   • If guess(mid) returns -1, the target number is lower, so adjust high.
   • If guess(mid) returns 1, the target number is higher, so adjust low.
3. Repeat until the number is found.

This algorithm ensures a logarithmic time complexity due to the halving of the search interval in each step.

Code

Here is the implementation in C++:

// Forward declaration of guess API.
int guess(int num);

class Solution {
public:
    int guessNumber(int n) {
        int low = 1, high = n;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int res = guess(mid);
            
            if (res == 0) {
                return mid;
            } else if (res == -1) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        
        return -1; // This line should never be reached if input is valid.
    }
};

Time Complexity

The time complexity of the binary search algorithm is O(log n):

• In each iteration, the search range is halved.
• Thus, to reduce the range down to 1 element, it takes at most log2(n) iterations.

The space complexity is O(1) as only a fixed amount of extra space (variables low, high, mid, res) is used.

This approach ensures efficiency and simplicity in finding the correct number.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?