• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
int nthUglyNumber(int n) {
vector<int> uglyNums{1};
int i2 = 0;
int i3 = 0;
int i5 = 0;

while (uglyNums.size() < n) {
const int next2 = uglyNums[i2] * 2;
const int next3 = uglyNums[i3] * 3;
const int next5 = uglyNums[i5] * 5;
const int next = min({next2, next3, next5});
if (next == next2)
++i2;
if (next == next3)
++i3;
if (next == next5)
++i5;
uglyNums.push_back(next);
}

return uglyNums.back();
}
};
``````

## JAVA

``````class Solution {
public int nthUglyNumber(int n) {
List<Integer> uglyNums = new ArrayList<>();
int i2 = 0;
int i3 = 0;
int i5 = 0;

while (uglyNums.size() < n) {
final int next2 = uglyNums.get(i2) * 2;
final int next3 = uglyNums.get(i3) * 3;
final int next5 = uglyNums.get(i5) * 5;
final int next = Math.min(next2, Math.min(next3, next5));
if (next == next2)
++i2;
if (next == next3)
++i3;
if (next == next5)
++i5;
}

return uglyNums.get(uglyNums.size() - 1);
}
}
``````

## Python

``````class Solution:
def nthUglyNumber(self, n: int) -> int:
nums = [1]
i2 = 0
i3 = 0
i5 = 0

while len(nums) < n:
next2 = nums[i2] * 2
next3 = nums[i3] * 3
next5 = nums[i5] * 5
next = min(next2, next3, next5)
if next == next2:
i2 += 1
if next == next3:
i3 += 1
if next == next5:
i5 += 1
nums.append(next)

return nums[-1]
``````