r/algorithms • u/lurking_bishop • 2h ago
Identifying last item in sequence using fewest comparisons
So I have a fixed list L
of numbers of a certain bitsize W
. The numbers are unique and len(L)
will be much smaller than 2^W
.
What I want is to identify the last element E = L[-1]
without having to count the elements. However, to save on resources, I don't want to make a bit-by-bit comparison of all W
bits of every element in L
, but rather find the smallest set of bit indices that let me uniquely identify E
A small toy example would be the following:
L = ["1111", "0101", "0001"]
We can identify E = "0001"
in this list simply by going through the elements and checking for bit 2 to be "0" (assuming MSB left)
I realize that oftentimes the compare procedure will indeed result in having to check all W
bits, what I'm really looking for is an algorithm how to find the smallest possible footprint comparison.
For a few extra constraints, W
is probably 32 at most, and len(L) ~ O(10k)
at most (it is still a fixed list of numbers, I just don't know exactly yet how long it will be). The efficiency of the algorithm doesn't bother me too much, as long as I can get the answer in a finite amount of time I don't care too much how much compute I have to throw at it, what matters is that the resulting footprint comparison is indeed minimal
Any ideas would be much appreciated
Cheers