# [Google Interview] Guess The Number Higher or Lower

Are you preparing for your next coding interview? If your answer is yes, then here’s a very interesting interview question for you that might come up in your interview.

## 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 function 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 == num).

Return the number that I picked.

⚠️Constraints:

• `1 <= n <= 231 - 1`
• `1 <= pick <= n`

Let’s have a look at some examples to improve our understanding of this problem.

## Examples

Now that you have understood the problem, let’s dive into the methods to solve the problem.

Prerequisite: If you are using a local editor, use the following function as the pre-defined function “guess”:

```def guess(num):
if pick < num:
return -1
elif pick > num:
return 1
else:
return 0```

## Method 1: Using Linear Search

Approach: The simplest approach would be to apply the linear search algorithm to guess whether the number is higher or lower. Go through every number and if it is equal to the pick, return the number.

Algorithm

1. Initialize a variable `no` to `0`.
2. Check for every number till `no < = n` to find if the guess is equal to the pick
3. Return the current number when the predefined function guess returns the value `0`.

Solution: Let’s look at the code.

```def guess_no(n, pick):
no = 0
while no <= n:
if guess(no) == 0:
return no
no = no + 1```

Test Case Analysis: Let’s run this code on our examples.

``````# Example 1
n = 10
pick = 6
print(guess_no(n, pick))
# 6

# Example 2
n = 1
pick = 1
print(guess_no(n, pick))
# 1

# Example 3
n = 20
pick = 10
print(guess_no(n, pick))
# 10

# Example 4
n = 10
pick = 9
print(guess_no(n, pick))
# 9``````

Complexity Analysis: In the worst-case scenario, the picked number is the last guessed number. In this case, the time complexity of this method will be O(n).

## Method 2: Using Divide and Conquer

Approach: In this approach, you have to divide `n` in half and search for the “`guess`” in another half by passing the variable “`mid`” value to the predefined function guess. Thus the idea of this approach is to divide the given range and then conquer the guessed number. Doesn’t it look like an implementation of the binary search algorithm?😉

Algorithm:

1. Initialize the low and high as `0` and `n + 1`.
2. Calculate the mid-value as `(low + high)//2` and pass it to the pre-defined guess function.
3. If the value returned by the function is `0`, return `mid`.
4. If the returned value is `1`, update the value of `low` to `mid + 1`.
5. If the returned value is` -1`, update the value of `high` to `mid - 1`.

The following diagram represents the working principle of the above algorithm with the help of an example.

Solution: Let’s look at the code:

```def guess_no(n, pick):
low, high = 0, n
while low <= high:
mid = (low + high) // 2
if guess(mid) == 0:
return mid
else:
if guess(mid) == 1:
low = mid + 1
else:
high = mid – 1```

Test Case Analysis: Let’s run this code on our examples.

``````# Example 1
n = 10
pick = 6
print(guess_no(n, pick))
# 6

# Example 2
n = 1
pick = 1
print(guess_no(n, pick))
# 1

# Example 3
n = 20
pick = 10
print(guess_no(n, pick))
# 10

# Example 4
n = 10
pick = 9
print(guess_no(n, pick))
# 9``````

Hurrah! It passed all the test cases.

Complexity Analysis:

• Time Complexity: We have used the divide and conquer strategy in this method, hence the time complexity of this method will be O(log n).
• Space Complexity: The space complexity of this method remains constant, i.e O(1).

## Bonus Solution: Using Ternary Search

Approach: The approach is almost similar to the binary search with the only difference that we divide `n` into three parts in this method. Use two mid variables to guess whether the number is high or low.

Algorithm:

1. Initialize the `low` and `high` as `0` and` n + 1`.
2. Calculate the `mid1` and `mid2` value as `low+(high - low)//3` and `high-(high-low)//3` respectively.
3. Pass both the mid-values to the predefined guess function. If the value returned is `0`, pass the respective mid-values.
4. Else, update the `low` and `high` values.

Solution: Let’s look at the code.

```def guess_no(low, high):
low, high = 0, n

while low <= high:
mid1 = low + (high - low) // 3
mid2 = high - (high - low) // 3
if guess(mid1) == 0:
return mid1
if guess(mid2) == 0:
return mid2
if guess(mid1) + guess(mid2) == 0:
low = mid1 + 1
high = mid2 - 1
elif guess(mid1) == -1:
high = mid1 - 1
else:
low = mid2 + 1```

Test Case Analysis: Let’s run this code on our examples.

``````# Example 1
n = 10
pick = 6
print(guess_no(n, pick))
# 6

# Example 2
n = 1
pick = 1
print(guess_no(n, pick))
# 1

# Example 3
n = 20
pick = 10
print(guess_no(n, pick))
# 10

# Example 4
n = 10
pick = 9
print(guess_no(n, pick))
# 9``````

Complexity Analysis:

• Time Complexity: The ternary search is similar to the Binary search method with the time complexity of O(log3n) ~ O(logn).
• Space Complexity: The space complexity of this method remains constant, i.e O(1).

## Conclusion

I hope you enjoyed this coding interview question. Please stay tuned and subscribe for more interesting coding problems.

✍️ Post Credits: Shubham Sayon and Rashi Agarwal 