Finding nth expressible numbers [reviewed]

Problem

Given set of the prime numbers, P , find the nth biggest number that can be expressed with the numbers in P.

 e.g. prime set = {2, 3} , expressible numbers = { 1, 2, 3, 4, 6 .. } , Given N = 3, the 3rd largest expressible number is 3.

Let's see how we can list expressible numbers, given two prime numbers: 2,3

{ 1, $1 \times 2$, $1 \times 3$, $2 \times 2$, $2 \times 3$, $3 \times 2$, $3 \times 3$, ...}

Starting from each numbers, we multiply either 2 or 3 to produce the next numbers repeated. If we draw this in the graphs, it would look like this.

1. Finding the pattern

Figure 1. Expressible number tree.

It seems we can do BFS to produce the numbers. Only thing we need to do is to store the numbers each time for later use.

2. Duplicate numbers

As you can see this way of producing the expressible numbers generate the duplicate numbers in each level in the tree,

Do we need to worry about that considering that we need to find N th largest numbers?

We can use HashTable or Set (in C++) to avoid adding the duplicate numbers. Does it worth? I don't think so.

3. When to stop

Now, we need how to produce the expressible numbers. One question that would strike your mind would be "when should I stop?". Given input, N, we can stop between 2N and 3N, considering the duplicate and possible "out of order" situation. Both 2N and 3N results in the same running time.
Let produce 3 times more numbers than N.

4. Sorting the numbers and find Nth largest numbers

Now we have 3* N expressible numbers. Last thing we need to do is to sort them in ascending order.
Question states that "find Nth largest numbers", but it seems to be misstated, it would be Nth smallest numbers from the beginning of the array.

Given sorted numbers, we can literate over the list until we encounter the Nth smallest element.
One caveat is that the array contains duplicate numbers. Therefore, we need to keep track of the unique numbers we encounters and return 10th unique number, which may not be in 10th position in the array

Over all running time of this algorithm is $O( N \log N)$, where N is the input parameter due to the sorting in the step 4.

Here is the complete code, running in $O(N \log N)$



Practice statistics:

5:08 : to come up with the vaguely right algorithm.
22:42: to hand-wrote the algorithm in the paper
16:36: to implement the useless MinHeap, which was not necessary at all.

Initial algorithm was completely wrong. Overlook how the primes should be multiplied.

Afterward, fixed the algorithm and achieved $O(N \log N)$ running time


UPDATE(2019-07-26): solved the problem again with python. Could not come up with algorithm in 10 minutes.

Here is a python version of solution.


Statistics:

15:00 to write the code.
3:00 to debug the code. made silly typo for variable and forgot the usage of deque()