Imagine we have a set of integers $$$x_1$$$ < $$$x_2$$$ < $$$x_3$$$ < ... < $$$x_n$$$. And let $$$d$$$ = $$$x_n$$$ — $$$x_1$$$. The pairwise distance between $$$x_i$$$ and $$$x_j$$$ is simply $$$|x_i - x_j|$$$. We need to compute the set of the values of the list of all pairwise distances, i.e. find $$$S = $$$ { $$$a \, | \, \exists i, j: |x_i-x_j|=a$$$ }.

For example, if we have integers {$$$1, 3, 4, 6$$$}, the set of all pairwise distance values is {$$$1, 2, 3, 5$$$}, because $$$|3-4| = 1$$$, $$$|1-3| = 2$$$, $$$|1-4| = 3$$$, $$$|1-6| = 5$$$ and there is no pair with a distance $$$4$$$.

The naive algorithm is apparently $$$O(n^2) \le O(d^2)$$$, whereas the best possible algorithm is at least $$$O(d)$$$, since there can be at most $$$d$$$ possible integer distances.

I came up with a bitmask algorithm, that has around $$$d^2/64$$$ operations.

I wonder if there is an asymptotically faster algorithm? I have been struggling for long, but I could not find any.