Find the duplicates in a list of floating point numbers
-
04-11-2019 - |
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