[Algorithms] Finding numbers

Posted on 2004-09-03
Last Modified: 2010-04-17
Suppose x, y (distinct) belongs to a set of integers from 0 to n-1.

Consider a  game bwetween players A and B. PLayer A keeps the 2 numbers x, y. B wants to find out x, y by asking questions.

a) Suppose A will reply either Yes or No. At least how many quetions B must ask to determine x, y?
    My ans which i think is not correct: log (n) + log (n-1)
    Any suggestions?

b) Suppose B can ask A in the following way:
       B gives A  a number r.
       A tells B whether x > r, and whether y > r.

    Hence for one question asked by B, there are 4 possible outcomes from A.
    What's a good algorithm for B?

Question by:acrilas
  • 2
LVL 23

Accepted Solution

brettmjohnson earned 43 total points
ID: 11979126
We really shouldn't do your homework for you, but you have at least made an effort.
Suppose you guess a number r, 0 <= r < n.

In case a) you have a 1/n chance of guessing the correct number, but if you are wrong
you have no other information to help you narrow your search, so the number of valid
answers is reduced by just 1.   On average, it would take you n/2 + n/2 guesses to
determine x and y.  Worst case would be 2n guesses (suppose x and y were both n-1).

In case b) if you guess wrong, you can subset the numbers.  Suppose your initial guess
is r = n/2, and it is wrong, say A says x < r.  In that case you can eliminate half of the
possible answers - limiting the next guess between 0 and r-1 (do you sense recursion here?).
This is called a binary search (dividing the solution space in half each time).  I leave it up
to you to determine the maximum number of comparisons needed to determine both
values in this case.

LVL 23

Expert Comment

ID: 11979128
> so the number of valid answers is reduced by just 1.

That, of course, should read:

so the number of *possible* valid answers is reduced by just 1.

LVL 100

Assisted Solution

mlmcc earned 41 total points
ID: 11982758
Can B ask A any type of Yes/No question?

If so A simple binary search will find each number in the fewest questions.
Question 1 - Is X less than (n-1) / 2
If Yes
Question 2 - Is X less than (n-1) / 4
If No
Question 2 - Is X less than (n-1) - (n-1) / 4
Repeat for Y.

0 - 128
Is X < 64?
Is X < 32?
Is X less than 96?

B. Will work similarly once x < guess and y > guess

For part A - Actually the way you have written the question, the answer is 1 question must be asked.  You may need more but only one question must be asked.
Is x= Guess1 and y = Guess2?  If correct you are done.



Assisted Solution

meessen earned 41 total points
ID: 11994852
Don't know why my comment wasn't posted.

For question A, your answer is correct and proves that you knew about binary search.

For question B, the answer is less trivial.
Here is my reasoning.
You may consider that you search x and in the same time get some information on the value on y.
So in any case you need log(n) questions to locate x.

Now what to do with the information you get on y. You have to consider two possible answer: get same answer for x and y or get a different answer for x and y. If you get a different answer this means that r is between x and y.
When you start with r = n/2 as you would do to search x, you will also know if y is on same side of r or on the opposite side. In any case you will have reduced the search space for y by two. But if y is on the opposite side of r, any subsequent question to locate x won't give you usefull information to locate y. In this case you will need an additional log(n/2) questions to locate y. There are 50% chances that this case happen. Or on the average 50% searches will cost you log(n)+log(n/2) questions.

Now if you learn after the first question that x and y are on the same side. Then you save a question for y. Ask then the next question for x. If we get then a different answer for y, we then need log(n/4) additional questions to locate y. This will happen 25% of the time (=0.5*0.5).

Thus the number of questions can be easily generalised into log(n) + 0.5*log(n/2) + 0.25*log(n/4) + 0.125*log(n/8) + ...

This can be generalised into

sum for i = 0 to log(n) of log( n/(2^i))/(2^i)

The term can be reorganised into [ log(n) - log(2^i) ] / (2^i) = [log(n)-i]/2^i
You can split this into two sums so that you have

log(n)*sum(1/2^i) - sum(i/2^i)
The first sum is equal to 1-1/(2^log(n)) which is also equal to 1-1/n

So the number of questions to ask is log(n)(1-1/n) - sum(i/2^i)
I could not find how to simplify the second term.

Hope this helps and that my comment gets published !


Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Does the idea of dealing with bits scare or confuse you? Does it seem like a waste of time in an age where we all have terabytes of storage? If so, you're missing out on one of the core tools in every professional programmer's toolbox. Learn how to …
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…

920 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now