Guess Number Higher or Lower

EASY

Description

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

Checkout 2 different approaches to solve Guess Number Higher or Lower. Click on different approaches to view the approach and algorithm in detail.

Linear Search

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).

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.

/** 
 * 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
 *               0 if num is equal to the picked number
 * public int guess(int num);
 */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        for (int i = 1; i <= n; i++) {
            if (guess(i) == 0) {
                return i;
            }
        }
        return -1; // Should not be reached based on problem constraints
    }
}

Complexity Analysis

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

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Guess Number Higher or Lower. Click on different languages to view the code.

/** * 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 ; } }

Video Solution

Watch the video walkthrough for Guess Number Higher or Lower

Algorithms:

Binary Search

Companies:

Samsung |