Question

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?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top