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


Markus Triska wrote:
"eKo1" <berndlosert@xxxxxxxxxxxx> writes:

example?

Say multiset of numbers is {1,2,3,1}. Initially, bitvector is:

... 0 0 0 0 0

First number is 1, so we set bit one in the bitvector:

... 0 0 0 1 0

Next number: 2; we (also) set bit two:

... 0 0 1 1 0


Next number (i.e., 3):

... 0 1 1 1 0

Next number is 1, and bit one is already set => numbers non-distinct.

Thanks for the example. However, I find two problems with this
approach:
1. We don't know a priori the size of the vector.
2. This doesn't handle real numbers.

.