Algorithm for finding 2 items with 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(x-y) <= (max(A)-min(A))/n

I need to create an algorithm for finding the 2 items (if there are more, any couple is good) in O(n) time.

I've been trying for a few hours and I'm stuck, any clues/hints?

Answer 1

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

Okay.. think of the numbers as being points on a line. Then min(A) and max(A) define the start and end points of the line respectively. Now divide that 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 don't need to rely on the question telling us that there are two points that satisfy the criterion. There are always two points that satisfy it.

The algorithm itself: You can use a simplified form of bucket sort here, since you only need one item per bucket (hit two and you're done). First loop once through the array to get min(A) and max(A) and create an integer array buckets[n] initialized to some default value, say -1. Then go for a 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-down integer result of x / ((max(A)-min(A))/n).