It's pretty quiet here, so I'll just post any solution. Feel free to add restrictions.
Memory O(k), time O(k^(4/3)log k).
We put the number 1 in a priority queue. Then, we repeat the following steps k times.
1. Extract the smallest element x from the queue. 2. Output x. 3. Put 2x, 3x, and 5x into the priority queue.
One has to take care of de-duplication either at step 1 or at step 3, but this doesn't change the asymptotic complexity.
There are a=O(k^(2/3)) elements in the queue and each is b=O(k^(1/3)) bits long. Therefore, the memory complexity is O(ab) and the time complexity is O(kb log a).
It's pretty quiet here, so I'll just post any solution. Feel free to add restrictions.
ReplyDeleteMemory O(k), time O(k^(4/3)log k).
We put the number 1 in a priority queue. Then, we repeat the following steps k times.
1. Extract the smallest element x from the queue.
2. Output x.
3. Put 2x, 3x, and 5x into the priority queue.
One has to take care of de-duplication either at step 1 or at step 3, but this doesn't change the asymptotic complexity.
There are a=O(k^(2/3)) elements in the queue and each is b=O(k^(1/3)) bits long. Therefore, the memory complexity is O(ab) and the time complexity is O(kb log a).