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

"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.



Best wishes,
Markus Triska

.