Hotter Colder

Interview

Time limit5sMemory limit256 MB

Summary

Jack must find Jill's hidden number between 1 and N using only hotter, colder, or same feedback on each guess.

Level: Medium5 of 10
Topics: Binary search, Math
Solved: No attempts yet

Problem

Jack and Jill play a game called Hotter, Colder. Jill has a number between 1 and N, and Jack makes repeated attempts to guess it.

Each of Jack's guesses is a number between 1 and N. In response to each guess, Jill answers hotter, colder or same. For Jack's first guess, Jill answers same. For the remaining guesses Jill answers:

hotter if this guess is closer to Jill's number than his previous guess
colder if this guess is farther from Jill's number than his previous guess
same if this guess is neither closer to nor further from Jill's number than his previous guess.

You are to implement a procedure HC(N) that plays Jack's role. This implementation may repeatedly call Guess(G), with G a number between 1 and N. Guess(G) returns 1 to indicate hotter, -1 to indicate colder or 0 to indicate same. HC(N) must return Jill's number.

Examples1

Example 1
Input
```
1 1
```
Expected output
```
1
```