Guess Number Higher or Lower

Solving this LeetCode coding problem with a “whirling” algorithm

Problem: We are playing a 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 3 possible results:

• -1: The number I picked is lower than your guess (i.e. pick < num)
• 1: The number I picked is higher than your guess (i.e. pick > num)
• 0: The number I picked is equal to your guess (i.e. pick == guess)

Return the number that I picked.

Example:

Input: n = 10, pick = 6 | Output: 6

After reading the problem, you can see that we are initially in the dark; because there is no way we can tell the number the computer picked directly. That number could be anything from 1 to n and if n is a very big number, the problem looks even scarier. Fortunately for us, we don’t have to be making random guesses or even loop through 1 to n to find the number the computer picked: the int guess(int num) API is going to direct us to the computer’s pick.

Initial attempt to solve the problem

Intuitively, we would want to pick any number at all (it could be a random integer in the range of 1 to n or it could be the middle-most number in the range since that would be the closest number to all the other numbers) and then use the API to determine which direction of the computer’s pick relative to the number. We would then move to the next number in the direction of the computer’s pick until we arrive at it. Essentially, if the computer’s pick is greater than the number we guessed (i.e. the API returns 1), we would increase our guess by 1 but if the computer’s pick is lesser than the number we guessed (i.e. the API returns -1), we would decrease our guess by 1. We would keep doing this until the API returns 0 and then we return the guess because that’s the computer’s pick.

Figure 1: Python implementation of the algorithm from the first solution

In some sense, the algorithm above is not so different from looping through 1 to n just to arrive at the computer’s pick. Because in both cases you only increase or decrease your guess by 1 until you arrive at your destination. And so the algorithm is highly inefficient, time wise. When I submitted this solution, I received a time limit exceeded error on the 14th test case. The first number in figure 2 is n and the second number is the computer’s pick.

Figure 2: Submission detail for first solution

You can see that for this particular test case, unless you are extremely lucky (and you’re most likely not going to be because the chances of guessing a number close to the computer’s pick is very close to zero), it’s going to take the algorithm quite some time to find the computer’s pick. There was therefore the need for a smarter solution.

Final solution of the problem

The final solution is based on the initial attempt and it’s basically an improvement of it. In the initial attempt, we guess a number and then determine if the computer’s pick is in front of or behind the number we guessed. We then move towards the position of the computer’s pick until we arrive at it. The final solution, however, is different. Inspired by the whirl pool, the final solution first makes a random guess of what the computer’s pick might be. It then uses API to get a sense of where the computer’s pick is, and then make very big jumps in that direction. When it crosses over to the other side of the computer’s pick, it then reduces its jump size and heads back to the computer’s pick. It continues to do this until it spirals into the computer’s pick (i.e. the API returns 0). The current value of the guess is then returned.

Figure 3: Visual representation of how the algorithm works

In the image above, i is the computer’s pick and k is our initial random guess. From figure 3, you can see how our guess spirals into the computer’s pick.

Figure 4: Python implementation of the algorithm for the final solution

Figure 5: Performance of the final solution on LeetCode

One could suggest changing our initial guess to the middle most number in the range so that it’s most likely closer to the computer’s pick. But due to the nature of this algorithm, doing that will not make that much of a difference in the performance of the algorithm.

Conclusion

We initially attempted this problem by creating an algorithm that moves in one direction towards the computer’s pick when given the position of the computer’s pick by the API. We later discussed a smarter algorithm that spirals in big jumps into the computer’s pick.

I’m very happy with the solution I devised but I’m curious to know if there are any other solutions out there or other ways of implementing the solution we have here so that it performs better. Do well to comment your thoughts in the comment section :)

Leave a clap if you enjoyed this. Happy Holidays!