Guess Number Higher or Lower

Difficulty: Easy | Acceptance: 57.50% | Paid: No Topics: Binary Search, Interactive

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

• -1: Your guess is higher than the number I picked (i.e., num > pick).
• 1: Your guess is lower than the number I picked (i.e., num < pick).
• 0: your guess is equal to the number I picked (i.e., num == pick).

Return the number that I picked.

• Examples
• Constraints
• Binary Search
• Ternary Search
• Linear Search

Examples

Example 1

Input:

n = 10, pick = 6

Output:

6

Example 2

Input:

n = 1, pick = 1

Output:

1

Example 3

Input:

n = 2, pick = 1

Output:

1

Constraints

1 <= n <= 2³¹ - 1
1 <= pick <= n

Binary Search

Intuition Since the numbers are sorted from 1 to n and we get feedback on whether our guess is too high or too low, binary search is the optimal approach to find the target in O(log n) time.

Steps

• Initialize left pointer to 1 and right pointer to n
• While left <= right, calculate mid using left + (right - left) / 2 to avoid overflow
• Call guess(mid) and adjust pointers based on the result
• Return mid when guess returns 0

class Solution:
    def guessNumber(self, n: int) -> int:
        left, right = 1, n
        while left <= right:
            mid = left + (right - left) // 2
            result = guess(mid)
            if result == 0:
                return mid
            elif result == -1:
                right = mid - 1
            else:
                left = mid + 1
        return -1

Complexity

• Time: O(log n)
• Space: O(1)
• Notes: Optimal solution with minimal API calls

Ternary Search

Intuition Ternary search divides the search space into three parts instead of two, using two midpoints to potentially eliminate two-thirds of the search space in each iteration.

Steps

• Initialize left to 1 and right to n
• Calculate two midpoints: mid1 at 1/3 and mid2 at 2/3 of the range
• Check both midpoints with the guess API
• Eliminate 2/3 of the search space based on the results

class Solution:
    def guessNumber(self, n: int) -> int:
        left, right = 1, n
        while left <= right:
            mid1 = left + (right - left) // 3
            mid2 = right - (right - left) // 3
            res1 = guess(mid1)
            res2 = guess(mid2)
            if res1 == 0:
                return mid1
            if res2 == 0:
                return mid2
            if res1 == -1:
                right = mid1 - 1
            elif res2 == 1:
                left = mid2 + 1
            else:
                left = mid1 + 1
                right = mid2 - 1
        return -1

Complexity

• Time: O(log₃ n)
• Space: O(1)
• Notes: Makes 2 API calls per iteration, so total calls are similar to binary search

Linear Search

Intuition A straightforward approach that checks each number from 1 to n sequentially until finding the correct answer.

Steps

• Iterate from 1 to n
• Call guess(i) for each number
• Return i when guess returns 0

class Solution:
    def guessNumber(self, n: int) -> int:
        for i in range(1, n + 1):
            if guess(i) == 0:
                return i
        return -1

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Inefficient for large n, will time out on LeetCode for maximum constraints