# Algorithm 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 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.

• "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? – xskxzr Dec 22 '19 at 2:10
• 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. – gnasher729 Dec 22 '19 at 14:16