```
struct Solution {
int nthUglyNumber(int n) {
vector <int> results (1,1);
int i = 0, j = 0, k = 0;
while (results.size() < n)
{
results.push_back(min(results[i] * 2, min(results[j] * 3, results[k] * 5)));
if (results.back() == results[i] * 2) ++i;
if (results.back() == results[j] * 3) ++j;
if (results.back() == results[k] * 5) ++k;
}
return results.back();
}
};
```

**Explanation:**

The key is to realize each number can be and have to be generated by a former number multiplied by 2, 3 or 5

e.g.

1 2 3 4 5 6 8 9 10 12 15..

what is next?

it must be x * 2 or y * 3 or z * 5, where x, y, z is an existing number.

How do we determine x, y, z then?

apparently, you can just *traverse the sequence generated by far* from 1 ... 15, until you find such x, y, z that x * 2, y * 3, z * 5 is just bigger than 15. In this case x=8, y=6, z=4. Then you compare x * 2, y * 3, z * 5 so you know next number will be x * 2 = 8 * 2 = 16.

k, now you have 1,2,3,4,....,15, 16,

Then what is next?

You wanna do the same process again to find the new x, y, z, but you realize, wait, do I have to

*traverse the sequence generated by far* again?

NO! since you know last time, x=8, y=6, z=4 and x=8 was used to generate 16, so this time, you can immediately know the new_x = 9 (the next number after 8 is 9 in the generated sequence), y=6, z=4.

Then you need to compare new_x * 2, y * 3, z * 5. You know next number is 9 * 2 = 18;

And you also know, the next x will be 10 since new_x = 9 was used this time.

But what is next y? apparently, if y=6, 6*3 = 18, which is already generated in this round. So you also need to update next y from 6 to 8.

Based on the idea above, you can actually generated x,y,z from very beginning, and update x, y, z accordingly. It ends up with a O(n) solution.