Guess Number Higher or Lower
Easy · Binary Search · Binary Search · Interactive
Problem
A number pick has been chosen secretly from 1 to n. You find it by calling the provided function guess(num), which compares your guess with the secret number and returns:
- -1 if your guess is too high (num > pick),
- 1 if your guess is too low (num < pick),
- 0 if you guessed it (num == pick).
Given n, return the secret number.
guess is already defined. In the tests, pick is given to the judge, which hides it behind guess; your function receives only n.
Examples
Input: n = 20, pick = 13 Output: 13
Guessing 10 returns 1, 15 returns -1, 12 returns 1, then 13 returns 0.
Input: n = 5, pick = 5 Output: 5
The secret number is the top of the range: 3 returns 1, 4 returns 1, 5 returns 0.
Input: n = 10, pick = 1 Output: 1
Guessing 5 returns -1, 2 returns -1, then 1 returns 0.
Constraints
- 1 <= n <= 2^31 - 1
- 1 <= pick <= n
Approaches
- Baseline: guess every number in turn — time O(n), space O(1)
Follow-up
Binary search needs at most ceil(log2(n + 1)) guesses, 31 for the largest n, and no strategy does better in the worst case: each answer splits the candidates into three parts, one of them a single number. If wrong guesses cost money (pay x for a wrong guess of x), the middle is no longer the best guess, and finding the cheapest strategy becomes an interval dynamic program.
Related problems
Start free on Cariara · Coding problems · System design studio
