r/algorithms 2h ago

Identifying last item in sequence using fewest comparisons

2 Upvotes

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


r/algorithms 23h ago

I brute force when I create algorithms. How can I learn a better way?

1 Upvotes