3 ms·

You can't because there's not enough RAM to hold all the numbers. So you'd be sorting the input as it arrives, yes, and then at some point you'd run out of RAM

• deleted 7y ago
  [deleted]
• vbezhenar 7y ago
  There's enough RAM to hold all the numbers. You just have to invent the representation to store all the numbers in the available RAM. Naive representation using 27 bits per number won't hold them all indeed. But if you would store them ordered and store difference rather than number using variable bit encoding, it would take less space. Just simple math: imagine that you have to store numbers 0, 100, 200, ..., 99 999 900 as a worst case scenario. As you're going to store the differences, you'll need to store "0" and then "100" 999999 times. If you would be able to represent "100" with 8 bits, you'll be able to keep your data inside 1 MiB limit. One simple encoding: 1xxxxxx for 7 bits; 01xxxxxxxx for 8 bits; 001xxxxxxxxx for 9 bits, etc. It should be enough for this task, although you could invent better encodings.
  • ecpottinger 7y ago
    That my idea too. It is very unlikely that the numbers are spread apart enough that you can't store the deltas in compact forms. Example starting your base as zero if the first number 100 you can store that in 1 byte, use the high bit to flag a larger number so if the next number is say 10000 you can store it in two bytes. But let's say the next number is 3000, you need to update the first delta, insert the new number and continue on. You probably can store most numbers that way.