algoadvance

Leetcode 374. Guess Number Higher or Lower

Problem Statement

You’re playing a guessing game with your friend. The game is as follows:

• You need to guess a number between 1 and n.
• Your friend will tell you whether your guess is:
  • Lower than the target number (indicating you need to pick a higher number)
  • Higher than the target number (indicating you need to pick a lower number)
  • Correct (indicating you have found the number)

Your goal is to determine the target number with the fewest guesses.

You are given a function int guess(int num) that returns:

• -1 if num is higher than the target number
• 1 if num is lower than the target number
• 0 if num is the target number

Your task is to implement the function int guessNumber(int n) that returns the target number.

Clarifying Questions

1. Range Clarity: Can I assume n is always greater than or equal to 1?
2. Input Validity: Can n be a very large number, necessitating concerns about performance?
3. Edge Cases: Should I handle cases where n is minimal (e.g., 1)?

Strategy

To efficiently determine the target number, we can use a binary search algorithm. By continually halving the search range based on feedback from the guess() function, we can pinpoint the target number in logarithmic time.

Steps:

1. Initialize two pointers, low and high, to 1 and n respectively.
2. While low is less than or equal to high:
   • Calculate the midpoint, mid.
   • Use the guess(mid) function to get feedback.
   • Adjust the search range based on the feedback.
3. When the guess(mid) function returns 0, we have found the target number and can return it.

Code

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int low = 1;
        int high = n;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;  // Avoid potential overflow
            
            int result = guess(mid);
            
            if (result == 0) {
                return mid;
            } else if (result == -1) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        
        // If no number is found (though per problem statements, this point shouldn't be reached)
        return -1;
    }
}

Time Complexity

The time complexity of the above solution is O(log n), thanks to the binary search approach. Each iteration halves the search space, leading to a logarithmic number of iterations relative to the size of n.

Summary

• Problem: Guess a target number between 1 and n using minimal comparisons.
• Solution: Implement binary search utilizing the guess() function for feedback.
• Complexity: The solution runs in O(log n) time, which is efficient for even large values of n.

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?