Sponsored
Sponsored
This approach uses binary search to guess the number. We maintain two pointers, low and high, representing the current range of numbers we need to search. Then, we guess the middle number of the range and adjust our range based on the response from the guess API. If the guessed number is correct, we return it. Otherwise, we adjust the low or high pointers and repeat the process until the number is guessed correctly.
Time Complexity: O(log n)
Space Complexity: O(1)
1#include<stdio.h>
2
3int guess(int num);
4
5int guessNumber(int n) {
6 int low = 1, high = n;
7 while (low <= high) {
8 int mid = low + (high - low) / 2;
9 int res = guess(mid);
10 if (res == 0)
11 return mid;
12 else if (res < 0)
13 high = mid - 1;
14 else
15 low = mid + 1;
16 }
17 return -1; // should not reach here
18}The code uses a binary search to find the number picked. The guess function simulates the API call that returns whether the guessed number is too high, too low, or correct.
This approach is a straightforward linear search that iterates from 1 to n guessing each number one by one until it finds the correct pick. It's simple but not efficient for larger values of n and is provided here primarily for educational purposes.
Time Complexity: O(n)
Space Complexity: O(1)
1class Solution {
public:
int guessNumber(int n) {
for (int i = 1; i <= n; i++) {
if (guess(i) == 0) {
return i;
}
}
return -1; // should not reach here
}
};This solution iteratively tries each possible number from 1 to n until the guessed number matches the picked number.