2
$\begingroup$

I receive a list of real numbers ( float ) between $0$ and $1$. The list has length $N+1$ and I need to find two numbers on the list which are $\le \frac{1}{N}$ apart. Here is an example test case:

[ 0.        ,  0.31662479,  0.63324958,  0.94987437,  0.26649916,
  0.58312395,  0.89974874,  0.21637353,  0.53299832,  0.84962311,
  0.1662479 ,  0.48287269,  0.79949748,  0.11612227,  0.43274706,
  0.74937186,  0.06599665]

One possibility I came up with is to multiply by $N=17$ and to take the integer part:

[ 0,  5, 10, 16,  4,  9, 15,  3,  9, 14,  2,  8, 13,  1,  7, 12,  1]

Then I have to find the location of two numbers in this list which are identical.


I would appreciate any solution to this problem with or without the intermediate multiplication step. Or does this problem have a particular name in the field of algorithms?

$\endgroup$
  • 4
    $\begingroup$ Can't you just sort the list and compare adjacent entries? I guess I don't understand your question very well. $\endgroup$ – adrianN Aug 1 '16 at 13:17
  • 1
    $\begingroup$ This is clever, but doesn't work if the numbers in your list are 0, 1/n, 2/n, 3/n, ..., (n-1)/n, 1. $\endgroup$ – gnasher729 Aug 1 '16 at 16:19
  • $\begingroup$ In addition to adrianN's comment, what does the title have to do with the body? It sounds like you want to find nearby numbers in a list of floating point numbers, or possibly duplicates in a list of integers... but not duplicates in a list of floating point numbers. $\endgroup$ – D.W. Aug 1 '16 at 19:40
3
$\begingroup$

Sorting

The simplest algorithm is to sort your floats, then compare adjacent entries. This will let you find all pairs that are $\le \frac1N$ apart in $O(N \lg N)$ time.

Hashing

It's also possible to come up with a linear-time algorithm, i.e., to check whether there is any nearby pair of floats and if so find at least, in $O(N)$ time.

Let $M=\lfloor N/2 \rfloor$. Build a list of integers by replacing each float $x$ with $\lfloor Mx \rfloor$, then find all duplicates in the resulting list of integers. Finding duplicates in a list of integers can be done in expected linear time by hashing and looking for a pair with the same hash. For each duplicate integer, check whether it corresponds to a pair of floats that differ by $\le \frac1N$.

Then, do it again: build a second list of integers by replacing each float $x$ with $\lfloor Mx + 0.5 \rfloor$, then find all duplicates in this list and check each to see whether it corresponds to a pair of floats that differ by $\le \frac1N$.

It's possible to show that if there exists a pair of floats that differ by $\le \frac1N$, then this procedure will find at least one such pair; and if there aren't any such pair, then this procedure will discover that fact. Moreover, with suitable choice of the hash function, this can be made to run in expected linear time. In fact, if you replace the hashing with counting sort, this runs in deterministic linear time.

In practice

In practice, my advice is to simply sort and then compare adjacent entries. It will be easier to implement, less fiddly (you don't have to deal with corner cases), obviously correct, and probably more than fast enough in practice.

$\endgroup$
1
$\begingroup$

This is a special situation: If we have n+1 values from 0 to n, there must be two values that are only 1/n apart. You can obviously find these by sorting the array and checking for two elements close together in O (n log n), but you can do faster.

There is a well known algorithm for finding medians or percentiles roughly based on the Quicksort algorithm: You start with an array with indices from 0 to n-1. One step of the Quicksort algorithm divides the array into a smaller and a larger half. Quicksort would then sort each half. Instead you decide which half contains the median or percentile you're interested in and process that half. You can do something similar.

Start with l = 0, r = n, low = 0, high = 1: The array elements at indices l to r are all >= low and <= high, and this implies there is a pair at most 1/n apart.

With the Quicksort algorithm, you would find an array element p (the pivot) and move all elements <= p to the left, all elements >= p to the right. You will get a [k] = p for some k. Then the elements from l to k are all between low and p, the elements from k to r are all between p and high. One of these ranges will guarantee two elements at most 1/n apart, so you change l, r, low, high accordingly.

You need to take some precautions to make this work: First, repeat this method until r - l ≤ 2. If r - l ≤ 2, sort the array and get the right values.

In the Quicksort algorithm, it can happen that little progress is made. In this algorithm, if you are not careful, no progress is made. If the pivot is chosen equal to low or high, no progress will be made. In that case, pick a second pivot, then a third. Lucky enough, if you picked three pivots equal to low or high, then you found a solution!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.