# Tag Info

Accepted

### Find two numbers in array $A$ such that $|x-y| \leq \frac{\max(A)-\min(A)}n$ in linear time

This is an interesting question. Here is a linear-time algorithm. Assum $n\ge1$. Compute the minimum $m$ and the maximum $M$. If $m=M$, return $a_0$ and $a_1$. Otherwise, let $\delta=\frac{M-m}n$. ...
• 39k

### Find two numbers in array $A$ such that $|x-y| \leq \frac{\max(A)-\min(A)}n$ in linear time

Let $z$ be the median of $A$, and split $A$ into two subarrays $B,C$: the array $B$ consists of all numbers at most $z$ (including $z$), and the array $C$ consists of all number at least $z$ (...
• 278k

### Compute median in unsorted array in $\mathcal{O}(\log{}n)$ space and $\mathcal{O}(\log{}n)$ passes

The natural algorithm determines the $\log n$ bits of the median, MSB to LSB. Suppose that we have determined the $k$ MSBs of the median, $b_{m-1},\ldots,b_{m-k}$. Determine the number of integers in ...
• 278k
Accepted

### Finding Median value given a tuple (value, frequency) in O(n) worst case time complexity

I think you can still use the linear time selection algorithm (median of medians) here. Let's call this algorithm $Select$ and let the median position be $m$, which is initially equal to $n/2$.Recall ...
• 2,780