Leetcode – Guess Number Higher or Lower Solution in Python

Spread the love

Introduction

In this article, we will take an in-depth look at “Guess Number Higher or Lower” problem on Leetcode and explore various methods to solve it using Python.

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.

Analyzing the Problem

The problem requires us to guess a secret number between 1 and n by making calls to an API. The API tells us if our current guess is too high, too low, or correct. Our task is to find the secret number using the least number of guesses. Let’s explore different strategies to approach this problem:

Approach 1: Linear Search

The simplest approach is to start from 1 and make consecutive guesses until the secret number is found. This method is simple, but very inefficient, especially for large values of n.

# The guess API is already defined.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num: int) -> int:

def guessNumber(n: int) -> int:
    for i in range(1, n+1):
        if guess(i) == 0:
            return i

The time complexity of this approach is O(n), which is not efficient for large values of n.

Approach 2: Binary Search

A more efficient approach is to use binary search. The binary search algorithm is highly effective in this scenario because the API tells us if our guess is too high or too low. By dividing the search space in half after each guess, we can find the secret number in logarithmic time.

def guessNumber(n: int) -> int:
    left, right = 1, n
    
    while left <= right:
        mid = left + (right - left) // 2
        
        result = guess(mid)
        
        if result == 0:
            return mid
        elif result == 1:
            left = mid + 1
        else:
            right = mid - 1

This approach has a time complexity of O(log n), which is a significant improvement over the linear search approach.

Approach 3: Ternary Search

Ternary search is an advanced version of binary search where the array is divided into three parts instead of two. It can be slightly faster than binary search, as it makes fewer comparisons in the best case.

def guessNumber(n: int) -> int:
    left, right = 1, n
    
    while left <= right:
        mid1 = left + (right - left) // 3
        mid2 = right - (right - left) // 3
        
        res1, res2 = guess(mid1), guess(mid2)
        
        if res1 == 0:
            return mid1
        elif res2 == 0:
            return mid2
        elif res1 < 0:
            left = mid1 + 1
        elif res2 > 0:
            right = mid2 - 1
        else:
            left = mid1 + 1
            right = mid2 - 1

The time complexity of ternary search is O(log n), similar to binary search, but with a smaller constant factor.

Best Practices and Optimization

Binary search and ternary search are the most efficient algorithms for solving this problem. However, binary search is generally preferred in practice because it is simpler and has better cache performance due to accessing contiguous memory locations.

Additionally, it is important to handle edge cases properly. In this problem, there are no edge cases that need to be considered separately as the problem clearly defines the input range.

Testing Your Solution

After implementing the chosen algorithm, it is good practice to test your solution against various test cases to ensure its correctness. Remember to test edge cases like the smallest and largest possible n. Moreover, try to test the algorithm’s efficiency by testing with a large n.

Conclusion

In this article, we’ve analyzed the “Guess Number Higher or Lower” problem from LeetCode and discussed various approaches to solve it, with binary search being the most efficient and practical. Understanding different algorithms and approaches is important for developing problem-solving skills, which is essential in coding interviews and real-world software development. Always remember to test your code against different test cases to ensure its robustness and correctness.

Leave a Reply