Guess Number Higher or Lower

Guess Number Higher or Lower is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Binary Search Patterns pattern, in the On Sorted Array/List subpattern.

Problem statement

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 <= 231 - 1

- 1 <= pick <= n

Topics and companies

Topics: Binary Search, Interactive.

Reported in interviews at Apple.

How to practise Guess Number Higher or Lower on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(log n) - Each iteration of the binary search halves the search space, so the number of iterations is logarithmic in n. time and O(1) - Only a constant amount of extra space is used for variables (left, right, mid, res). space.

Open Guess Number Higher or Lower in the code editor, or read the Guess Number Higher or Lower editorial for a worked solution with its approach and complexity analysis.

Where Guess Number Higher or Lower sits in the DSA pattern sheet

• Binary Search Patterns pattern guide
• On Sorted Array/List subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Guess Number Higher or Lower

Other problems that use the same On Sorted Array/List and Binary Search Patterns techniques:

• Binary Search — Easy, same subpattern
• First Bad Version — Easy, same subpattern
• Kth Missing Positive Number — Easy, same subpattern
• Search a 2D Matrix — Medium, same subpattern
• Search Insert Position — Easy, same subpattern
• Single Element in a Sorted Array — Medium, same subpattern