Algorithm for finding two elements with a given difference in an array

Question

I am given an array of real numbers, A. It has n + 1 elements. It is known that there are at least 2 elements of the array x and y such that:

abs(xy) <= (max(A)-min(A))/n 

I need to create an algorithm to search for 2 elements (if there is more in O (n), any pair is good).

I tried for several hours and I got stuck, some kind of hints / tips?

Answer 1

woo I get it! The trick is in the Pigeonhole Principle.

Ok ... think about how numbers are dots on a line. Then min(A) and max(A) determine the start and end points of the line, respectively. Now divide this line into n equal intervals of length (max(A)-min(A))/n . Since there are n+1 points, two of them must fall into one of the intervals.

Note that we do not need to rely on a question telling us that there are two points that satisfy the criterion. There are always two points that satisfy this.

Algorithm itself: you can use a simplified sorting form in the form of a bucket, since you only need one element for each bucket (click two and you're done). The first loop through the array is to get min(A) and max(A) and create an integer array buckets[n] initialized with some default value, like -1 . Then go to the second pass:

 for (int i=0; i<len; i++) { int bucket_num = find_bucket(array[i]); if (bucket[bucket_num] == -1) bucket[bucket_num] = i; else // found pair at (i, bucket[bucket_num]) } 

Where find_bucket(x) returns the rounded integer result x / ((max(A)-min(A))/n) .

Answer 2

Let us reformulate the problem: we must find two elements such that abs(xy) <= c , where c is the constant that we can find in O(n) time. (Indeed, we can calculate both max(A) and min(A) in linear time and simply assign c=(max-min)/n ).

Suppose we have a set of buckets, so that 0<=x<c in the first bucket elements are placed, c<=x<=2c in the second bucket element, etc. For each element, we can define its bucket for O(1) time. Please note that the number of occupied buckets will not exceed the number of elements in the array.

Let iterate over the array and put each element in its bucket. If we are going to place it in the bucket, then there is already another element, then we just found the correct pair of x and y !

If we repeated the entire array, and each element fell into its own bucket, do not worry! Now change the buckets (no more than n , as we said above), and for each element bucket x , if the next element y contains such an element that abs(xy)<=c ve found a solution.

If we repeated all the buckets and did not find suitable elements, then there is no solution. OMG, I really missed this stuff for pigs (see another answer ).

Buckets can be implemented as a hash map, where each bucket contains one array index (placing an item in the bucket will look like this: buckets[ a[i] / c] = i ). We calculate c in O(n) time, assign positions to buckets in O(n)*O(1) time ( O(1) is access to the hash map), move the buckets in O(n) time. Therefore, the entire algorithm is linear.