edited by
4,258 views
10 votes
10 votes

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?

  1. $10$
  2. $32$
  3. $100$
  4. $999$
  5. $\text{None of the above}$
edited by

6 Answers

10 votes
10 votes

By using binary search Asha needs only $  \left \lceil \text{log}_2 1000   \right \rceil = 10$ comparisons 

1 votes
1 votes
t is solved by using binary search.

time complexity of searching a number from 'n' numbers using binary search is (log n).

⌈log2 1000⌉  = 9.96 =  10 questions
1 votes
1 votes

 Natural numbers between 1 and 1000, so numbers are in sorted order. So we can apply Binary Search Algorithm to it.

Ref: https://www.geeksforgeeks.org/binary-search/

Time Complexity of the algorithm = $\Theta$($log_{2}$n ), n = Number of elements and $\Theta$($log_{2}$n ) = Number of times we performs comparison.

Here n = 1000 = ${2^{10}}$(Approx).

So the number of comparison in worst case = $\Theta$($log_{2}$${2^{10}}$ ) = 10 .      (You can use big-oh notation also).

Explanation: Every time Asha will ask to Lata → 

1)Is the number equals to mid? If yes then done.

else

2)Is the number greater than mid? If yes then we will check for greater elements and also mid will be changed.

else

3) We will check for smaller elements and also mid will be changed.

Actually he is doing nothing but binary search. Here mid is nothing but middle element of our current search area in those 1000 elements.Please check the algorithm it will be more clear.

 

Answer:

Related questions

10 votes
10 votes
2 answers
1
8 votes
8 votes
6 answers
2
5 votes
5 votes
2 answers
3
Arjun asked Dec 18, 2018
1,467 views
How many proper divisors (that is, divisors other than $1$ or $7200$) does $7200$ have ?$18$$20$$52$$54$$60$