4
$\begingroup$

Given a sorted array A, we have to find the position of an element m in it. (It is also given that the element exists in the array.)

However there is a constraint. Like in a game you have 3 lives. If you probe any element x > m in the array you will lose one life. You can probe as many elements you want which are smaller than m. If you find m, you win.

The solution to this should not be in linear time.

What I tried:

I will drop eggs from floors 1, 2, 4, 8.. And in log n time, I will find a sub-array in which m exists (at cost of 1 life). But this sub-array was of size at most n/2. I cannot repeatedly apply this process since, I have limited number of lives.

My thoughts

I am thinking that a solution does not exist to this problem which is faster than linear. How to prove this (if this is the case)? Can I create a contradiction from the assumption that a solution exists?

Improve this question
$\endgroup$
4
  • $\begingroup$ "should not be in linear time" -- so quadratic time would be fair? ;) $\endgroup$
    – Raphael
    Commented Aug 4, 2014 at 9:25
  • 1
    $\begingroup$ 1. Is the array in sorted order? If so, you should mention that in the question. 2. What have you tried? You should edit the question to show us what you have tried and where specifically you got stuck. Suppose you have 0 lives. Can you prove it then? (Show us the proof.) What if you have 1 life. Now can you prove it? OK, what about 2 lives.... $\endgroup$
    – D.W. ♦
    Commented Aug 4, 2014 at 9:43
  • $\begingroup$ @D.W. I did mention in question that array is sorted. $\endgroup$
    – Swapniel
    Commented Aug 5, 2014 at 13:02
  • 1
    $\begingroup$ There is an interesting jump from queries in an array to dropping eggs... $\endgroup$
    – gnasher729
    Commented Dec 16, 2016 at 10:03

1 Answer 1

Reset to default
8
$\begingroup$

If you have only one life only safe way is to check every element starting from minimal. It's $O(n)$

If you have two lives and limited with $k + 1$ comparisons the minimal element of array you can check first has index $k$, so we still have $k$ comparisons to check all previous elements one by one, if no lives was lost than next element to check has index $k + (k - 1)$ so total numbers of elements we can check is that way $n = k + (k-1) + (k-2) + ... + 1 = \frac{k(k+1)}{2}$ So if you have two lives you can find target element for ($k = \frac{1 + \sqrt{1 + 8n}}{2}$) $+1$ comparisons. It's $O(\sqrt n)$

So if we have three lives and $k + 2$ comparisons first we should check element of index $\frac{(k + 1)(k)}{2}$ than if we will lost life we will be able to check all earlier elements for $k + 1$ comparisons. So in full analogy $n = \frac{(k+1)(k)}{2} + \frac{(k)(k-1)}{2} + \frac{(k-1)(k-2)}{2} + \frac{(k-2)(k-3)}{2} +... + \frac{3\cdot2}{2} + \frac{2\cdot1}{2} = \frac{1}{6}(k+2)(k+1)(k)$

Therefore $n> \frac{1}{6}(k)^3$ and $k < \sqrt[3]{6n}$

So we can solve this for $O(\sqrt[3]{n})$

This is variation of quite known skyscraper and glass or crystal balls puzzle, though I may be didn't find correct name for it in English.

Improve this answer
$\endgroup$
8
  • $\begingroup$ I don't quite follow your answer. If one "bad" comparison is allowed (i.e. we have $2$ lives), you should better check the mid-element, and then go through all the $\frac{n}{2}$ other elements if you lost a life. Worst-case complexity is $\frac{n}{2}+1$ total queries to the array, and in principle you can't do better than that. $\endgroup$
    – zarathustra
    Commented Aug 4, 2014 at 14:08
  • 1
    $\begingroup$ Not it's not better to check mid element, for example if you have 100 elements array numbered you check first 14th, if you failed you can check other elements for 14 comparisons (15 total). If you not failed you should check 14+13 = 27th and if you fail than, you will can check all elements between 14 and 27 for 13 comparisons (total 15). $\endgroup$
    – Lurr
    Commented Aug 4, 2014 at 14:22
  • $\begingroup$ than if you continue without losing life you will check 25+11 = 36th, to have 11 checks to check all elements between 25 and 36, 36+11 = 47, 47+10 = 57, 57 + 9 =66, 66 + 8 = 74 74 + 7 = 81, 81 + 6 = 87, 87 + 5 = 92, 92 + 4 = 96, 96 + 3 = 99, 99 + 2 > 100, so 15 comparisons is enough to find element in 100 elements array, which is much less than 50. $\endgroup$
    – Lurr
    Commented Aug 4, 2014 at 14:22
  • 2
    $\begingroup$ It's often known as the "egg drop problem". Unfortunately, while searching on this phrase turns up a lot of solutions, the majority seem to be either incomplete or wrong. (Of course, searching for "egg drop" lands you squarely in the context of Chinese cuisine.) $\endgroup$
    – Rick Decker
    Commented Aug 5, 2014 at 1:27
  • 1
    $\begingroup$ k is nearly number of comparisons, we can calculate max n for current k, make an equation and retrieve k(n) from this equation. $k = \frac{1 + \sqrt{1 + 8n}}{2}$; for 100 it's $\frac{1 + \sqrt{1 + 800}}{2} = 14.65$ $\endgroup$
    – Lurr
    Commented Aug 5, 2014 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.