3 ms·
Because we're restricted to O(1) extra space by the problem statement, regardless of the number of cards we're picking. We could be picking all 2^64, but defini
by SAI_Peregrinus 7y ago
Because we're restricted to O(1) extra space by the problem statement, regardless of the number of cards we're picking. We could be picking all 2^64, but definitely don't want the constant in O(1) to be 2^64!
- debatem1 7y agoO(1) /extra/ space, but we must have working space at least the size of the output.
- dmurray 7y agoThe paper describes an online one-pass algorithm for which this is not true: as you get each input value you accept or reject it. So you only need O(1) space to store the number of values you've seen, the number remaining, and the number you still need to accept.
- theelous3 7y agoThe number of values you've seen could be "only" an exabyte, which is a problem.
- thaumasiotes 7y agoYou're storing the number of values you've seen: So far, I've seen 172 values. You're not storing the values themselves. If the number of values you've processed is too large to fit in memory... you probably had to spend a long, long time processing those values. It's not a relevant objection.