# C++/DP solution but we have to use long instead of int

• ``````int nthUglyNumber(int n)
{
vector<long> ugly_nums = {1};
ugly_nums.reserve(n);
size_t created = 1;
size_t initial_gen = 0;
size_t i = 0;
long candidate,candidate_aux;

while(created < n)
{
candidate = LONG_MAX;
for (i=initial_gen;i<created;++i)
{

candidate_aux = 2*ugly_nums[i];
if (candidate_aux > candidate) break;
if (candidate_aux < candidate && candidate_aux > ugly_nums[created-1])
{
candidate = candidate_aux;
continue;
}
candidate_aux = 3*ugly_nums[i];
if (candidate_aux < candidate && candidate_aux > ugly_nums[created-1])
{
candidate = candidate_aux;
continue;
}
candidate_aux = 5*ugly_nums[i];
if (candidate_aux < candidate && candidate_aux > ugly_nums[created-1])
{
candidate = candidate_aux;
continue;
}
}
++created;
ugly_nums.push_back(candidate);
if (5*ugly_nums[initial_gen] < ugly_nums[created-1]) initial_gen++;
}
return ugly_nums[n-1];
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.