4 ms·
Can you elaborate on the second part? Are you saying you're going to expand the size of the universe by a factor of 2^(k-1) to use as locations of the "bars"?
by sirclueless 9y ago
Can you elaborate on the second part? Are you saying you're going to expand the size of the universe by a factor of 2^(k-1) to use as locations of the "bars"?
- nightcracker 9y agoYes, the universe is expanded.
- sirclueless 9y agoI really like this mechanism. It seems like it should be the optimal way to store a set of size k. Out of curiosity, do you know of an efficient way to calculate this without sorting first? Or even better, without knowing k ahead of time? If you can sort your input first it's trivial, but even though it seems like a super efficient way to store a set of numbers I don't know how to use it to solve, for example, the other problem in these comments of sorting 1M 32-bit integers in 2MB of RAM (you can store them with this mechanism in about 1.7MB of RAM, but only if they were already sorted).
- nightcracker 9y agoI don't know of a way of doing this without sorting or knowing k ahead of time, sorry.