Guess Game - provide best guessing strategy

• I pick a number from 1 to n. You have to guess which number it is. Every time you guess wrong, I'll tell you whether the number is higher or lower.

1. What is the best guessing strategy in this case?
2. Suppose that when you guess x, you pay \$x dollars. What is the best strategy now?

• @StefanPochmann: how would you do it?

• For 1. One approach could be to use binary search -log(n) guessing.

• @elmirap Right, that is pretty easy. What about the second question?

1. Binary search.
2. To not play.

• Oh wait, no... I'll guess x = -1000000000. Thank you.

• @StefanPochmann haha I mean, the strategy to spend the least amount of money.

• @StefanPochmann Do you mean , you tell the interviewer, I don't gamble, point :-)

• @elmirap I don't think it's even gambling. Because I have nothing to gain! But must pay to play. So why would I?

Oh well, I'll think about it...

• @StefanPochmann you gain the awe of the crowd, 'cuz you're smart since you play rationally. lol

• @StefanPochmann you will gain to lose the less, this is some form of damage minimization.
@agave do you think that Stefan will be allured by crowd awe?

• @elmirap yes, a lot.

• @agave Do you pick the number randomly and uniformly, or do you pick it in a certain way, trying to maximize your profit? Or can't I know?

• @StefanPochmann

I pick my number randomly. Say n = 100, you only know that I picked one of the numbers in {1, ..., 100}. That's all you know.
Say we play. I pick 84. If you then ask me "Is it 50?", you pay 50 and I say "it's higher than that!". So your interval is now [51, 100]. And so on, till you run out of money (haha) or you guess the right number.

Your target is to be smart and spend the least amount of money while playing this game (which ends when you guess the number I picked).

• @StefanPochmann I guess the question was intentionally vague to see if you ask the right questions.

• Lazy as I am, I coded an experiment and tried to see a pattern. There somewhat is a pattern, but there's also strange fluctuations.

Do you know the best strategy? (Don't tell what it is, I'd just like to know whether you know it.)

• @agave suppose that I have to guess a number in range (1,10) . What is the actual question. Find the minimum cost which I can pay with the best strategy? Can you give us an example for range (1,10)?Thanks I see that cost depends on the number to guess, but at the end there is a cost which is miimum for some number in range(1,10)

• @StefanPochmann yes, I do. I can give you a suggestion, if you want. The fact that a super genius like you is not seeing it immediately makes me think about how in the world the interviewer could assume that a good SWE must solve this question in 45 minutes... Every (very smart guy) I asked this question to wasn't able to answer.

• @elmirap Try to make an example by yourself. Take the array [1, 5] (simpler case) and see in the worst case how much you pay.

• @agave don't you have the answer of 1..5?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.