2

I've a problem I struggle to solve. The question is: Given an array A of size $n$, find a pair, $i,j$ so that $$ 0 \le A[i] - A[j] \le \frac{\max[A] - \min[A]}{n-1}$$ now the problem is that time complexity needs to be $O(n)$. Thx in advance

Ingix
  • 14,494
Stevie
  • 163
  • 5

1 Answers1

2

Find min $m$, find max $M$ and then create an array $B$ of $n-1$ elements full of $-1$. Now go through array and for each element $x$ with index $k$ find such $i$ that: $$m+i\frac{M-m}{n-1} \le x \le m+(i+1)\frac{M-m}{n-1}$$ And put $B[i]=k$ if previously we had $B[i]=-1$. If not, that means that the numbers ubder the indicies $B[i]$ and $k$ satisfy your conditions. Also we are bound to find such pair because there are more elements in the original table than in $B$ (pigeonhole principle).

Basically the idea is to divide the interval $[m,M]$ in $n-1$ equal parts and put all the numbers where they belong - there has to be a collision yielding our answer.

Bartek
  • 2,475
  • So if I understand correctly this idea is using the buckets like in a bucket sort. Thank you very much – Stevie Jul 07 '19 at 10:47
  • @YohaiM Exactly, since we need to find two elements sufficiently close to each other it's sufficient to divide the interval respectively. – Bartek Jul 07 '19 at 10:51