TIFR CSE 2019 | Part A | Question: 5

Question

Asha and Lata play a game in which Lata first thinks of a natural number between $1$ and $1000$. Asha must find out that number by asking Lata questions, but Lata can only reply by saying “Yes” or “no”. Assume that Lata always tells the truth. What is the least number of questions that Asha needs to ask within which she can always find out the number Lata has thought of?

• A. $10$
• B. $32$
• C. $100$
• D. $999$
• E. $\text{None of the above}$

Comments

Those who are not getting it,

This is nothing but Binary Search, therefore the answer is lg1000=9.96=10

---

We can ask only one question

Is the number less than Or equal to A[mid].

If ita answer is yes we will go left side otherwise go to right side

---

Given 1-1000 natural numbers they  all are sorted first point to keep in mind so we can apply binary search on it to find an element in the least number of steps 

We need to reach the one single element that is may be lets say it is 501 

so we need to reach a point where we have only one element   so 

by Writing it through equation it can be written as

 (n/2power k)=1

n=2 power k

Here n=1000

1000=  2 power k 

applying log  on both sides we get k =10

n/2 means we are dividing something into half so to reach some certain point we need to it k times so it would boil down to n/2power k

 

---

Those who are not getting why binary search they can try this…

Assume whatever number Lata thinks Asha said to take the binary representations of it.

Now, Asha starts from right hand side (little endian approach) and each time asking is it 0 or not.

if YES then write 0

else NO write 1.

Note: you can also ask for 1.

Now, since 1 to 1000 numbers are used we can represent all up to using 10 binary digits/bits.(range will be 1 to 1023)

_ _ _ _ _ _ _ _ _ _   (placeholders for 10 digits)

So, 10 is the answer.

Answer 1

Binary representation of number 1000 will have 10 digits as 1000<1024 $(2^{10})$, which is a sequence of 1's and 0's corresponding to a yes or a no !!!

Answer 2

It is similar to binary search as the she can ask questions if the number is smaller or grater then a perticular number (since natural numbers are sorted)

so the answer would be $\log_2 (1000)$ =  9.98 ~ 10

so the answer is: A