3 ms·
> Given that 7 guesses covers 128 numbers I might be confused, but don't 7 guesses actually cover 255 numbers? I think you have to count all nodes in the searc
by hulium 2y ago
> Given that 7 guesses covers 128 numbers
I might be confused, but don't 7 guesses actually cover 255 numbers? I think you have to count all nodes in the search tree, not only the leafs, because you can get the correct number before reaching a leaf node.
Or more generally k guesses cover 2^(k+1)-1 numbers,
e.g. with one guess you get the answers correct/high/low, which can cover 3 numbers)
Maybe there is a mistake in my thinking, because this would mean you can cover 127 numbers with 6 guesses so you could not lose the original game.
Edit: My mistake is that you still have to explicitly guess even if you know the precise answer already, so you cannot cover 3 numbers with 1 guess. This means 7 guesses cover 127 numbers.
- deleted 2y ago[deleted]
- sltkr 2y agoYour logic is correct but you are off-by-one. 1 guess gets you 1 number, so the formula is 2^k - 1, and 7 guesses thus covers 127 numbers. You can also view it as a recurrence: f(1) = 1 f(n) = 2*f(n - 1) + 1 = 2^n - 1 But your binary search tree example is more intuitive.
- hulium 2y agoYes, you are right. In this game, you can know the answer after 6 guesses, but then you also have to tell him, which counts as the 7th guess.
- hamburglar 2y agoYou are correct that you can know the answer in 6, but actually winning requires you to “guess” that one last time once you know it.