Task 2: Number Series

/*
    File: main.cpp

    Task: Limited prime factor series

    Author: *REDACTED*

    Created: *REDACTED*

    Desc: File containing the main function implementing a solution to task 2 of the assessment
    dealing with generating a limited prime factor series.
*/


#include <iostream>
#include <algorithm>
#include <conio.h>
#include <vector>
#include <assert.h>

#define DEBUG 0;

using namespace std;


// Main function generating the desired value at a given position in the series
/*
    Algorithm:
    * model the problem as a need to generate numbers of the form { 2^i * 3^j * 5^k }, for all possible i, j, k, in increasing order
    * start with i, j, k being 0, then increment one at each step, ensuring the smallest result is chosen
    * populate a growing series with the result of each step, and reference previous values in order to keep track of incrementing powers
    * return the last value populated when the required series position is reached

    Notes:
    - Initially implemented passing in the 'resultsVector' by reference, allowing it to be used outside the scope of this method
    - Eventually decided to keep the actual generated list local, since no specification was provided for actually having access to the series after its populated
*/
int ProvideValueAtPosition(int position)
{
    // The resultsVector will be populated with the series as its increasing
    vector<int> resultsVector = { 1 };

    // Track the position we are looking for, start at 1 since we are adding '1' to the vector by definition
    int counter = 1;

    // Track the power indicies for the required primes i.e. 'i' tracks powers of 2, 'j' of 3, etc
    int i, j, k;
    i = j = k = 0;

    // Build the series up to the requested position
    while (counter < position)
    {
        // Find the minimum next value for the series, depending on the preceeding values and powers of the primes
        int nextValue = min({ 2 * resultsVector[i], 3 * resultsVector[j], 5 * resultsVector[k] });
        resultsVector.push_back(nextValue);

        // Increment the power indicies depending on which prime was the smallest
        if (nextValue == 2 * resultsVector[i])
        {
            i++;
        }

        if (nextValue == 3 * resultsVector[j])
        {
            j++;
        }

        if (nextValue == 5 * resultsVector[k])
        {
            k++;
        }

#if DEBUG
        cout << endl;
        cout << "counter: " << counter << endl;
        cout << "nextValue: " << nextValue << endl;
        cout << "{i, j, k}: " << "{ " << i << ", " << j << ", " << k << " }" << endl;
#endif
        counter++;
    }

    return resultsVector.back();
}

int main()
{
    cout << "Task 2: Limited prime factor series \n" << endl;

    // The required position of the series we are looking for
    int requiredPosition = 1500;

    int result = ProvideValueAtPosition(requiredPosition);

    cout << "Value at position: " << requiredPosition << " is: " << result << endl;

    // Assert whether we got the correct value for position 1500
    if( requiredPosition == 1500 )
        assert(result == 859963392);

    // Dirty getch to see terminal output before termination
    _getch();
    return 0;
}