Saturday, May 7, 2011

Lucky numbers

Lucky numbers are numbers whose prime factors are just 2, 3, 5. Find the first k lucky numbers.
Pubblicato da a
Reazioni: 

1 comment:

  1. 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).

    ReplyDelete

Subscribe to: Post Comments (Atom)