Find the Nth Expressible Number of Given Set of Prime Numbers

1. Problem Description
This is a Google interview question for software develop engineer from careercup. Here is the orignal thread,
"

Given a prime set, we call "prime expressible" if a number can be factorized only using given prime numbers. Find n-th big expressible number. 

E.g., prime set = {2, 3}
expressible number = {1,2,3,4,6,8, 9, 12...}
non-expressible number = {5, 10... }

The primes in the prime set are ordered in an increasing order, and can include a prime < 10^4 (don't remember the exact range), and n can also be as large as 1-10^6.

- pandacoder 20 days ago in United States | Report Duplicate | Flag ".

2. Algorithm
Assume a given set of prime numbers in ascending order, P1, P2, ..., Pm. The expressible number can be any of these: P1^X1 * P2^X2 * ... * Pm^Xm,
    where X1, ... Xm are non-negative integers.
The first M+1 expressible number will be {1, P1, ..., Pm}. If N is not more than M+1, then it is easy to find the value.

Otherwise the expressible number has to be tracked when they grow bigger. A linked-list is used for each prime number to track the expressible number for each prime number as L1, L2, ..., Lm. For any number Eji in Lj has to meeting the following condition,
    - X1, ..., Xj must not be all zero, Xj+1 ... Xm must all be zero.
This guarantees that,
    - The number in L1: P1^X1, where X1 is positive integers
    - L2: P1^X1*P2^X2, where X1 and X2 are positive integers
    - L3: P1^X1*P2^X2*P3^X3, where X1, X2 and X3 are positive integers
    ......
    - Lm: P1^X1*P2^X2*...*Pm^Xm, where X1, X2, ..., Xm are positive integers

At the same time the number is tracked when inserted into L.
    - If N is ranged in [1, m+1], return from {1, P1, ..., Pm}
    - Otherwise,
    - Initialize Nth = 1
    - Starting with {P1}, {P2}, ..., {Pm} for L.
    - Find the smallest value, Es,  of the min heap, MH, that is made of the head of L.
      As MH - {P1, P2, ..., Pm} at the start.
    - Find the corresponding prime number against which linked list Es comes from, Px and Lx
    - Append Es*Px into Lx, Es*Px+1 into Lx+1, ..., Ex*Pm into Lm
    - Remove Es from Lx and increment the Nth
    - Repeat above 4 steps until Nth reaches N.

3. Example
Given prime number sets: {2, 3, 5}
Find the 12th expressible number.

Example 1 - 1

Example 1 - 2

4. C++ Implementation and Test
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <list>
#include <queue>
#include <unordered_map>

struct KeyValuePair
{
    KeyValuePair()
    {}

    KeyValuePair(unsigned long val,
                 unsigned long k,
                 size_t index)
        :value(val), key(k), keyIndex(index)
    {}

    KeyValuePair(const KeyValuePair&) = default;
    KeyValuePair& operator=(const KeyValuePair&) = default;

    unsigned long value = 2;
    unsigned long key = 2;
    size_t keyIndex = 0;
};

struct KeyValuePairComparator
{
    bool operator()(const KeyValuePair& lhs, const KeyValuePair& rhs) {
        return lhs.value > rhs.value;
    }
};

using MinHeap = std::priority_queue<KeyValuePair,
                                    std::vector<KeyValuePair>,
                                    KeyValuePairComparator>;
using ValueMap = std::unordered_map<unsigned long, std::list<unsigned long>>;

unsigned long FindNthExpressibleNumGivenSet(const std::vector<unsigned long>& sortedPrimes,
                                            const unsigned long Nth,
                                            MinHeap& topNums,
                                            ValueMap& nums)
{
    unsigned long numCounter = Nth - 1;

    auto iterStart = sortedPrimes.begin();
    auto iterEnd = sortedPrimes.end();
    unsigned long value;
    while (true) {
        const KeyValuePair kvp = topNums.top();
        nums[kvp.key].pop_front();
        // pop out a value from the priority queue
        // count until the Nth
        --numCounter;
        if (numCounter == 0) {
            return kvp.value;
        }
        // Generate the number and push them into the list
        for (auto iter = iterStart + kvp.keyIndex; iter != iterEnd; ++iter) {
            value = *iter * kvp.value;
            nums[*iter].push_back(value);
        }
        // pop out the value from the priority queue
        // and push its successor from the value list into the priority queue
        topNums.pop();
        topNums.push(KeyValuePair(nums[kvp.key].front(), kvp.key, kvp.keyIndex));
    }

    return 0;
}

unsigned long FindNthExpressibleNumGivenSet(const std::vector<unsigned long>& sortedPrimes,
                                            const unsigned long Nth)
{
    if (sortedPrimes.empty() || Nth == 0) {
        // indicates failure
        return 0;
    }

    if (Nth == 1) {
        return 1;
    }

    if (Nth <= sortedPrimes.size() + 1) {
        return sortedPrimes[Nth - 2];
    }

    MinHeap topNums;
    ValueMap nums;
    auto iterEnd = sortedPrimes.end();
    size_t idx = 0;
    // Starting point:
    // the values: each prime number x 1
    // the priority queue is (prime number, prime number) - <value, key> pair
    for (auto iter = sortedPrimes.begin(); iter != iterEnd; ++iter, ++idx) {
        std::list<unsigned long> values;
        values.push_front(*iter);
        nums[*iter] = values;
        topNums.push(KeyValuePair(*iter, *iter, idx));
    }

    return FindNthExpressibleNumGivenSet(sortedPrimes, Nth, topNums, nums);
}

// ********************************************************************************
// Test
// ********************************************************************************
#include <cassert>
void TestFindNthExpressibleNum()
{
    std::vector<unsigned long> sortedPrimes;
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 0) == 0);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 1) == 0);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 5) == 0);

    sortedPrimes.push_back(2);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 0) == 0);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 1) == 1);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 2) == 2);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 3) == 4);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 4) == 8);

    sortedPrimes.push_back(3);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 0) == 0);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 1) == 1);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 2) == 2);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 3) == 3);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 4) == 4);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 5) == 6);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 6) == 8);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 7) == 9);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 8) == 12);

    sortedPrimes = {3, 5, 7};
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 0) == 0);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 1) == 1);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 2) == 3);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 3) == 5);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 4) == 7);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 5) == 9);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 6) == 15);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 7) == 21);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 8) == 25);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 9) == 27);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 10) == 35);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 11) == 45);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 12) == 49);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 13) == 63);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 14) == 75);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 15) == 81);
}