All Puzzles: Here
Puzzle: Shankar chooses a number between 1 and 10,000. Geeta has to guess the chosen number as quickly as possible. Shankar will let Geeta know whether her guess is smaller than, larger than or equal to the number. The caveat is that Geeta loses the game if her guess is larger than Shankar’s chosen number two or more times. (A) How many guesses are necessary? (B) What if Shankar is allowed to pick an arbitrarily large positive number?
Source: Heard from Ovidiu Gheorghioiu at Google in 2007.
Solution: (A) When Shankar chooses a number between 1 and n, Geeta should start guessing √n, 2√n, 3√n, 4√n, and so on. The first time her guess exceeds Shankar’s number, the range of numbers has been narrowed down to √n numbers; she then starts guessing sequentially in that range.
(B) If Shankar guesses an arbitrarily large number n, then Geeta may guess 1, 4, 9, 16, 25, and so on, to discover k such that Shankar’s number lies between k2 and (k+1)2. Then guess k2+1, k2+2, k2+3 and so on. On the whole, this requires O(√n) steps.
Dear Gurmeet,
In the last paragraph of the solution is a small typo:
Then guess k+1, k+2, k+3 and so on.
should be
Then guess k^2+1, k^2+2, k^2+3 and so on.
Nothing big, but still… :-)
Kind regards,
Yuri.
Thanks for identifying the typo, Yuri! It has been fixed.
Wrong.
Consider N=10000, guess=100, and told “bigger.”
Geeta guesses 200 next (2*sqrt(10000.) But the search space is now N-guess = 9900, so according to the solution, the optimal next guess should be sqrt(10000)+sqrt(9900).
Note this isn’t a minor round-off error. If Shankar picks 9950, note how absurd Geeta’s 99th guess is.
Hi Gorobei, the solution is not recursive. So with n = 10000, Geeta would start guessing 100, 200, 300, 400, and so on.
Please note that n does not denote the ’search space’ but the maximum number that Shankar might have chosen.
Gurmeet,
Thanks for the prompt reply.
Consider this case: Geeta has just guessed 9800, no wrong answers so far. The remaining space is 9801..10000. The proposed solution says his next guess is 9900.
Now consider the case of N=200, the space is 1..200 – same size, same information content. In this eqivalent situation, Geeta guesses 14.
Unless I’m misunderstanding the problem, 14 != 100, and k*sqrt(n) is non-optimal.
Yes, the solution is not optimal. The proposed algorithm provides an upper bound on the optimal number of steps.
Perhaps there is a technique (and an algorithm) to prove the lower bound as well. Please let me know if you discover it! Thanks.
The algorithm is fairly simple.
Essentially, f(N) =
guess/N * guess/2 [the linear search] +
(1-guess/N) * f(N-guess) [the recursion.]
Then, we search for the best guess for each N.
After fixing up the math a bit to handle the edge cases, and drinking several beers, we see that for N=10000, our first guess is about 138, with 94 expected guesses.
The take-home point is that our hop-size decreases over time: it’s a balance between the linear and non-linear parts of the equation.
The answer is very simple.
In worst case the guess should be k, k+k-1, k+k-1+k-2, k+k-1+k-2+k-3,…….. subsequently so that being bigger than value Shankar has chosen the total number of guesses are k.
And k is such that k*k+1 >= 2n
For example let n=45 then k=9 as 9*10 =45*2
In this case total no. of guesses is always 9.
This is optimal worst case solution
I feel she should guess in powers of two.
That is 2^0,2^1 and so on.
Let us say the number where he says the guess is greater is 2^m then she should start guessing from 2^m linearly.
that should complete the problem in log(n) with some constant
The solution should be a balance between linear search and the non-linear jump function……
instead of using the √n, 2√n, 3√n, 4√n, and so on or, 1, 4, 9, 16, 25, and so on…. as the step function( both of which will take a maximum of 199 guesses), we can use the decreasing function……
say that we start at some K,
keep guessing with,
K , K+(K-1), K+ K-1) +(K-2), …….. 1. which would take at the worst case K number of steps
we have to find the optimal. For that we have to find the minimum K for which, 1 + 2 + 3 + 4 +……+k >10000
for which we have to solve the equation k^2 +k – 20000 > 0
This would be satisfied by K =141
This value is better than the other solutions discussed above which would give a worst case of 199 guesses.
So the guesses must be,
141, 281, 420, 538…… 9994, 9997, 9999, 10000
by following this approach the maximum guesses required is √(n/2). but it is still in the order of O(√n)
I’m not sure if we would get a better solution by taking a guess function, K, K +(K- i) , K + (K – i) + (K – 2*i)……
where i>1
can someone try this one??
Note: i was wrong when i told that the function is a decreasing function….. what i meant was that the increment in the function is decreasing by one.
A)
Anand’s idea is better….
Example:
Using The solution suggested by Gurmeet, for “spanning” all the numbers till 100,
reaching 99 would take 19 guesses (10, 20, 30, 40, 50, 60, 70, 80, 90, 100 (oops), 91, 92, 93, 94, 95, 96, 97, 98, 99)
you actually need only 14 guesses to span all the numbers:
For 99 it would be :
14
27 (14+13)
39 (14+13+12)
50 (14+13+12+11)
60
69
77
84
90
95
99
96
97
98
The idea is if you start with
k
k+(k-1)
k+(k-1)+(k-2)
.
.
.
1
Spanning all numbers take k guesses
So, sigma k >= N
So, min value of k is the minimum solution of k for sigma (k) >= n
Hence, for 100 its 14 and not 19 as suggested by Gurmeet’s solution…
Sorry for the long comment :D
This problem is exactly same as the egg dropping problem we study in common algorithms courses ….
You have two eggs and how would you get the max floor from which egg would not break in minimum number of tries…
The solution I suggested in the previous comment is just a modification of the algorithm in the current setting
yeah, Pratik solution is the correct and optimize solution for such problems
Thanx :D