Guess Number Higher or Lower - Practice Coding Problems

Guess Number Higher or Lower - Problem

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 (the number I picked stays the same throughout the game).

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.

Input & Output

Example 1 — Basic Case

$ Input: n = 10, pick = 6

› Output: 6

💡 Note: Using binary search: guess 5 (too low), then 8 (too high), then 6 (correct). Found in 3 guesses.

Example 2 — Edge Case

$ Input: n = 1, pick = 1

› Output: 1

💡 Note: Only one number possible, so first guess is correct.

Example 3 — Large Range

$ Input: n = 2, pick = 1

› Output: 1

💡 Note: Binary search starts with middle (1.5 → 1), which happens to be correct.

Constraints

1 ≤ n ≤ 2³¹ - 1
1 ≤ pick ≤ n

Visualization

Tap to expand

Understanding the Visualization

Input

Range [1, n] and unknown picked number

Binary Search

Guess middle, adjust range based on API response

Output

Return the picked number

Key Takeaway

🎯 Key Insight: Binary search eliminates half the possibilities with each guess, making it logarithmically efficient

Asked in

G Google 25 f Facebook 18 M Microsoft 15 a Amazon 12

The key insight is to use binary search to eliminate half the search space with each guess. The optimal approach uses binary search with O(log n) time complexity and O(1) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Linear Search	O(n)	O(1)	Try every number from 1 to n until we find the answer
Binary Search	O(log n)	O(1)	Use binary search to eliminate half the search space with each guess

Linear Search — Algorithm Steps

Start with guess = 1
Call guess(guess) and check result
If not 0, increment guess by 1
Repeat until we find the answer

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with guess = 1

Check

Call guess API and get response

Increment

Move to next number if not found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Simulated guess API - in actual problem this is provided
int pickedNumber = 0;

int guess(int num) {
    if (num > pickedNumber) return -1;
    if (num < pickedNumber) return 1;
    return 0;
}

int solution(int n) {
    for (int i = 1; i <= n; i++) {
        int result = guess(i);
        if (result == 0) {
            return i;
        }
    }
    return -1;
}

int main() {
    int n;
    scanf("%d", &n);
    // For simulation, extract picked number from second line
    scanf("%d", &pickedNumber);
    
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

In worst case, we might need to guess all numbers from 1 to n

✓ Linear Growth

Space Complexity

O(1)

Only using a single variable to track current guess

✓ Linear Space

28.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler