#374

Easy

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Guess Number Higher or Lower

Find the picked number efficiently using binary search while adjusting guesses based on higher or lower feedback in this interactive game.

binary search interactive

Problem Statement

You are playing a guessing game where a number between 1 and n is selected, and your task is to identify it with minimal guesses. Each time you make a guess, you receive feedback indicating whether the secret number is higher, lower, or equal to your guess.

Implement a function that interacts with the guess API to determine the picked number. Your solution must efficiently reduce the search space using the feedback, leveraging the binary search pattern to achieve optimal guesses for any valid n.

Examples

Example 1

Input: n = 10, pick = 6

Output: 6

Example details omitted.

Example 2

Input: n = 1, pick = 1

Output: 1

Example details omitted.

Example 3

Input: n = 2, pick = 1

Output: 1

Example details omitted.

Constraints

1 <= n <= 231 - 1
1 <= pick <= n

Solution Approach

Initialize Search Bounds

Start with low = 1 and high = n. These bounds define the current search space, ensuring each guess halves the remaining possibilities.

Binary Search Iteration

While low is less than or equal to high, guess the midpoint. Use the feedback from the guess API to update low or high, shrinking the search space toward the picked number.

Return the Picked Number

Once the feedback indicates a correct guess, return that number. This guarantees you find the target efficiently, avoiding unnecessary guesses and leveraging the logarithmic nature of binary search.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(log n) since each guess reduces the search space by half. Space complexity is O(1) because only the low, high, and mid variables are stored.

What Interviewers Usually Probe

Expect you to explain why binary search fits this interactive guessing scenario.
They may ask about edge cases like n = 1 or pick at the boundaries.
Interviewers often check whether you handle integer overflow when computing mid = low + (high - low)/2.

Common Pitfalls or Variants

Common pitfalls

Using (low + high)/2 directly can cause integer overflow for large n.
Not updating low or high correctly based on the guess feedback leads to infinite loops.
Failing to consider that pick could be at the initial bounds causes off-by-one errors.

Follow-up variants

Modify the game to allow a range of valid picks and find any number in that range.
Implement a version where guesses have a cost, requiring minimal total guess cost.
Adapt the binary search approach to a descending ordered pick range instead of ascending.

FAQ

What is the best strategy to solve Guess Number Higher or Lower?

Applying a binary search over the valid range ensures the minimal number of guesses and efficiently narrows the search space.

Can the picked number be at the bounds?

Yes, pick can be 1 or n, so your binary search must handle edge cases correctly without skipping bounds.

Why is using (low + high)/2 potentially dangerous?

It may overflow for large n values; instead, compute mid as low + (high - low)/2 to stay safe.

Does the algorithm require extra memory?

No, the search maintains only low, high, and mid variables, giving O(1) space complexity.

How does GhostInterview assist with this binary search pattern?

It guides you through adjusting search bounds interactively, ensuring correct application of the binary search pattern and avoiding common off-by-one errors.

terminal

Solution

Solution 1: Binary Search

We perform a binary search in the interval $[1,..n]$, and find the first number that satisfies `guess(x) <= 0`, which is the answer.

1

2

3

4

5

6

7

8

9

10

11

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
#          1 if num is lower than the picked number
#          otherwise return 0
# def guess(num: int) -> int:


class Solution:
    def guessNumber(self, n: int) -> int:
        return bisect.bisect(range(1, n + 1), 0, key=lambda x: -guess(x))

Continue Practicing

#278 first bad version #1095 find in mountain array #1237 find positive integer solution for a given equation