264. Ugly Number II

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> p = {2, 3, 5};
        vector<long long> dp(n, numeric_limits<int>::max());
        dp[0] = 1;

        vector<int> last_pos(p.size(), 0);

        for (int i = 1; i < n; i++)
        {
            int pos = -1;
            for (int k = 0; k < p.size(); k++)
            {
                while(dp[last_pos[k]] * static_cast<long long>(p[k]) <= dp[i - 1])
                    last_pos[k] += 1;

                if (dp[last_pos[k]] * static_cast<long long>(p[k]) < dp[i])
                {
                    dp[i] = dp[last_pos[k]] * static_cast<long long>(p[k]);
                    pos = k;
                }
            }

            last_pos[pos] += 1;
        }

        return dp.back();
    }
};