Leetcode 374. Guess Number Higher or Lower

Problem Explanation

In this problem, the user is playing a guessing game. The target number is chosen by the game from a range of 1 to n and user is expected to guess the number. If user guess is wrong, the game will provide a hint if the number is either high or low. This hint is used to continue guessing until the correct number is selected. If the hint is -1, it means the target number is lower than the user guess. If it is 1, the target number is higher. If the hint is 0, it means the user has correctly guessed the number.

For example:

If n=10 and pick=6 and the user guesses 7, the hint returned will be -1. This means the user should guess a lower number. If the user guesses 5, the hint will be 1, which means the user's guess is low and he should guess a higher number. If the user then guesses 6, the hint will be 0. Thus, 6 is the target number.

The code already mentions a defined method guess(int num) that returns hints. Hence, we are not implementing it in our solutions.

Solution Explanation

The code uses binary search to solve this problem. It saves a lot of time as binary search helps in discarding half of the numbers in each iteration. This way, the algorithm does not need to check each number from 1 to n, but only needs to determine whether to change to a higher number or lower number based on the hint, thereby halving the search space each time.

The guessNumber function takes in the maximum number, n, as input and establishes the lowerbound l and the upperbound r. Inside the while loop, the function checks the middle number m and use it to call the guess method. If the method returns -1 or 0, assign l to the middle and otherwise assign r to m+1.

Java Solution

1
2java
3
4public class Solution extends GuessGame {
5    public int guessNumber(int n) {
6        int low = 1;
7        int high = n;
8        while (low <= high) {
9            int mid = low + (high - low) / 2;
10            int res = guess(mid);
11            if (res == 0)
12                return mid;
13            else if (res < 0)
14                high = mid - 1;
15            else
16                low = mid + 1;
17        }
18        return -1;
19    }
20}

Python Solution

1
2python
3def guessNumber(self, n):
4    low = 1
5    high = n
6    while low <= high:
7        mid = low + (high - low) // 2
8        res = guess(mid)
9        if res == 0:
10            return mid
11        elif res < 0:
12            high = mid - 1
13        else:
14            low = mid + 1
15    return -1

JavaScript Solution

1
2javascript
3var guessNumber = function(n) {
4    let low = 1, high = n;
5    while(low <= high){
6        let mid = Math.floor(low + ( high -low)/2);
7        let res = guess(mid);
8        if( res == 0){
9            return mid;
10        }
11        else if(res < 0){
12            high = mid -1;
13        }
14        else{
15            low = mid + 1;
16        }
17    }
18    return -1;  
19};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int guessNumber(int n) {
6        int low = 1;
7        int high = n;
8        while (low <= high) {
9            int mid = low + (high - low) / 2;
10            int res = guess(mid);
11            if (res == 0)
12                return mid;
13            else if (res < 0)
14                high = mid - 1;
15            else
16                low = mid + 1;
17        }
18        // if there is no such number, return -1
19        return -1;
20    }
21};

C# Solution

1
2csharp
3public class Solution {
4    public int GuessNumber(int n) {
5        int low = 1;
6        int 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                low = mid + 1;
14            else
15                high = mid - 1;
16        }
17        return -1;
18    }
19}

Ruby Solution

1
2ruby
3class Solution
4    def guessNumber(n)
5        low = 1
6        high = n
7        while low <= high do
8            mid = low + (high - low) / 2
9            res = guess(mid)
10            if res == 0
11                return mid
12            elsif res < 0
13                high = mid - 1
14            else
15                low = mid + 1
16            end
17        end
18        return -1
19    end
20end

Swift Solution

1
2swift
3class Solution {
4    func guessNumber(_ n: Int) -> Int {
5        var low = 1
6        var high = n
7        while low <= high {
8            let mid = low + (high - low) / 2
9            let 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        }
18        return -1
19    }
20}

Kotlin Solution

1
2kotlin
3class Solution: GuessGame() {
4    fun guessNumber(n:Int): Int{
5        var low = 1
6        var high = n
7        while (low <= high) {
8            val mid = low + (high - low) / 2
9            val 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
18    }
19}

Each of the solutions in various programming languages uses the same logic of implementing binary search to guess the number. This also shows the versatility of the binary search algorithm which can be applied in various situations when the problem involves a sorted or ordered sequence. The primary advantage of binary search is its efficiency, allowing the solution to run in log(n) time which is much faster than a linear search. Nevertheless, it is crucial to remember that binary search can only be applied when the sequence is sorted or ordered.