Suppose you are given a set of small boxes, numbered 1 to n, identical in every

Question

Suppose you are given a set of small boxes, numbered 1 to n, identical in every respect except that each of the first i contain a pearl whereas the remaining n ? i are empty. You also have two magic wands that can each test whether a box is empty or not in a single touch, except that a wand disappears if you test it on an empty box. Show that, without knowing the value of i, you can use the two wands to determine all the boxes containing pearls using at most o(n) wand touches. Express, as a function of n, the asymptotic number of wand touches needed.

Explanation / Answer

Function checkPearl(set){

Divide box into two equal sets

For(i=0i<set.length;i++){

    Do check with magicwand1 for first set1

    If pearl found

      again divide into two sets and check as above

Else

    Do check with magicwand2 for set2

    //iteratively do checking

}

}

So that now it uses at most c * sqrt(n) touches

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.