Guess Number Higher or Lower

Easy

#0361Time: O(n) - In the worst-case scenario, we might have to iterate through all the numbers from 1 to n.Space: O(1) - We only use a constant amount of extra space for variables.1 company

Algorithms

Binary Search

Companies

Samsung

Prompt

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.

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves checking every number sequentially from 1 up to n. We call the guess() API for each number until we find the correct one.

Algorithm

1. Iterate through numbers from i = 1 to n.
1. For each number i, call the guess(i) API.
1. If guess(i) returns 0, it means i is the correct number. Return i.
1. If the loop finishes, it means the number was not found (this case is not possible according to the problem constraints).

Walkthrough

We start by guessing the number 1. We then call the guess(1) API. If it returns 0, we've found the number. If not, we proceed to guess 2, then 3, and so on, until we reach n. This method is straightforward but very slow, as it might require up to n calls to the guess() API in the worst case.

1/** 2 * Forward declaration of guess API.3 * @param  num   your guess4 * @return 	     -1 if num is higher than the picked number5 * 		      1 if num is lower than the picked number6 *               0 if num is equal to the picked number7 * public int guess(int num);8 */9 10public class Solution extends GuessGame {11    public int guessNumber(int n) {12        for (int i = 1; i <= n; i++) {13            if (guess(i) == 0) {14                return i;15            }16        }17        return -1; // Should not be reached based on problem constraints18    }19}

Complexity

Time

O(n) - In the worst-case scenario, we might have to iterate through all the numbers from 1 to n.

Space

O(1) - We only use a constant amount of extra space for variables.

Trade-offs

Pros

Simple to understand and implement.

Cons

Highly inefficient for large values of n.
Will result in a 'Time Limit Exceeded' error on most coding platforms due to the n constraint being up to 2^31 - 1.

This is the optimal approach. It works by maintaining a range of possible numbers [low, high] and repeatedly guessing the middle number. Based on the API's feedback, we eliminate half of the range in each step, drastically reducing the search time.

Algorithm

1. Initialize two pointers, low = 1 and high = n.
1. Loop as long as low <= high.
1. Calculate the middle index: mid = low + (high - low) / 2.
1. Call the guess(mid) API.
1. If the result is 0, return mid.
1. If the result is -1 (guess is too high), it means the target is in the lower half, so update high = mid - 1.
1. If the result is 1 (guess is too low), it means the target is in the upper half, so update low = mid + 1.

Walkthrough

We initialize two pointers, low to 1 and high to n, which define our search space. In each step of the loop, we calculate the middle point mid. It's calculated as low + (high - low) / 2 to avoid potential integer overflow when low and high are large. We then call guess(mid).

If guess(mid) returns 0, we've found the number and can return mid.
If guess(mid) returns -1 (our guess is too high), we know the picked number must be in the lower half, so we update high = mid - 1.
If guess(mid) returns 1 (our guess is too low), the picked number must be in the upper half, so we update low = mid + 1. We repeat this process until low is no longer less than or equal to high, at which point we will have found the number.

1/** 2 * Forward declaration of guess API.3 * @param  num   your guess4 * @return 	     -1 if num is higher than the picked number5 * 		      1 if num is lower than the picked number6 *               0 if num is equal to the picked number7 * public int guess(int num);8 */9 10public class Solution extends GuessGame {11    public int guessNumber(int n) {12        int low = 1;13        int high = n;14        while (low <= high) {15            // Using (low + high) / 2 might cause overflow for large n16            int mid = low + (high - low) / 2; 17            int result = guess(mid);18            if (result == 0) {19                return mid;20            } else if (result == -1) {21                // My guess is higher than the picked number22                high = mid - 1;23            } else {24                // My guess is lower than the picked number25                low = mid + 1;26            }27        }28        return -1; // Should not be reached29    }30}

Complexity

Time

O(log n) - With each guess, we eliminate half of the remaining search space, leading to logarithmic time complexity.

Space

O(1) - We only use a constant amount of extra space for pointers and the middle value.

Trade-offs

Pros

Extremely efficient and optimal for this problem.
Handles large values of n easily within time limits.

Cons

Slightly more complex to conceptualize than a linear scan, but it's a fundamental algorithm.

Solutions

Solution

1/** * Forward declaration of guess API. * @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 * int guess(int num); */ public class Solution : GuessGame { public int GuessNumber ( int n ) { int left = 1 , right = n ; while ( left < right ) { int mid = left + (( right - left ) >> 1 ); if ( guess ( mid ) <= 0 ) { right = mid ; } else { left = mid + 1 ; } } return left ; } }

1/** * Forward declaration of guess API. * @param num your guess * @return -1 if num is lower than the guess number * 1 if num is higher than the guess number * otherwise return 0 * int guess(int num); */ public class Solution extends GuessGame { public int guessNumber ( int n ) { int left = 1 , right = n ; while ( left < right ) { int mid = ( left + right ) >>> 1 ; if ( guess ( mid ) <= 0 ) { right = mid ; } else { left = mid + 1 ; } } return left ; } }

1/** * Forward declaration of guess API. * @param num your guess * @return -1 if num is lower than the guess number * 1 if num is higher than the guess number * otherwise return 0 * int guess(int num); */ class Solution { public: int guessNumber ( int n ) { int left = 1 , right = n ; while ( left < right ) { int mid = left + (( right - left ) >> 1 ); if ( guess ( mid ) <= 0 ) { right = mid ; } else { left = mid + 1 ; } } return left ; } };

1# 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 ))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem