We have An array of $3n$ elements. we want to Find $x$ and $y$ for array of $3n$ numbers such that 1/3 are less than $x$. 1/3 between $x$ and $y$ and 1/3 greater than $y$. We can solve this problem of $M(n)$ space and $T(n)$ time complexity. We want to find $M(n)$ and $T(n)$ as functions of $n$. Note that $x$ and $y$ are not in array. for example if the array is $1 , 2 , 3, 4 , 5 ,6$ we can have $x=2.5$ and $y=4.5$. Also $x$ and $y$ are obviously not unique and we just want one number for each of them that satisfy the conditions. The array is not necessarily sorted.

For this problem, I was thinking of using order statistic and find $n$ and $n+1$ and $2n$ and $2n+1$ elements. But the problem seems odd to me. I know Selection algorithm is $O(n)$ but this problems seem more complex than just saying that.

It is the problem of a quiz of DS course (Of an Iranian University) but it seems like it is from a reference book. I want to know the answer of this question or reference to know what the question really wants and maybe finding the answer this way.

  • 2
    $\begingroup$ "I know Selection algorithm is O(n) but this problems seem more complex than just saying that." Why? Doesn't the selection algorithm solve your problem? $\endgroup$ – xskxzr Dec 22 '19 at 2:10
  • $\begingroup$ If the n-smallest and n+1-smallest or the n-largest and n+1-largest element are the same, then there is no solution. $\endgroup$ – gnasher729 Dec 22 '19 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.