Impostor_Syndrome's blog

Guessing the number in sqrt(n) time?
By Impostor_Syndrome, history, 2 years ago, In English

You are playing a game on a machine. First of all the machine chooses a number N. You do not know this number and you need to make guesses to find it. Suppose you choose the number k, the machine tells whether k is less than, equal to or greater than N. The game ends if k is equal to N. If you guess a number which is greater than N, then it is considered a bad guess. You cannot make more than 1 bad guess.

Expected time complexity is sqrt(n) time. I find it impossible to do, when only one bad guess is allowed. Any help would be appreciated.

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Let's call N the max possible value for n. Split the array of N possible values in sqrt(N) chunks of length sqrt(N). Now guess the biggest number in every chunk, starting with the smallest chunk and going towards the biggest chunk. When your guess fails(k > n), you know for certain n is somewhere within this chunk where you just failed. so you start at the beginning of this chunk and guess all the numbers, one by one, until the end of the chunk. You will make at most sqrt(n) 'BIG' guesses (the ones where you guess the end of the chunk) and sqrt(N) 'small' guesses, when you're in phase 2 and are guessing one by one the values in a certain chunk. This technique is called sqrt decomposition, it is very common.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Thank you, soo.. much. Heard of a technique names sqrt decomposition, but never read about it.

    → Reply
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

This is a mathematical problem. It was asked in the BlackBox event in my 1st year (we both have the same university xD).

Let me rephrase the question so that it becomes easier for you. You have 2 eggs and a tower having 100 floors, and the egg breaks when dropped from a threshold floor. What is the minimum number of operations required to find the threshold floor?

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Initially take sum=1 Then take c=1 And keep adding c to the sum and increase c by 1 everytime and keep checking. When sum exceeds n , sub c from sum once and increase sum by 1 until you get the answer

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This is a well-known problem called the "Egg dropping puzzle". There are several approaches to this problem which you can read about them here.

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I think this actually generalizes up to larger amounts of allowed incorrect guesses (sort of, things get tricky around log2(n)). For example, in the case where you can have two incorrect guesses your answer will be on O(cuberoot(n)) time.

→ Reply