Re: On the complexity of determining whether n numbers are distinct


Markus Triska wrote:
Maintain a bit-vector, initially set to 0. For each number n, check
whether n-th bit is set (if yes => non-distinct). Otherwise, set n-th
bit and continue. Requires no comparison between any of the numbers.

I'm not following you at all. Could you provide an example?

.