# 264. Ugly Number II

• Time: $O(n)$
• Space: $O(n)$
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public: int nthUglyNumber(int n) { vector 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(); } };
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public int nthUglyNumber(int n) { List uglyNums = new ArrayList<>(); uglyNums.add(1); 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; uglyNums.add(next); } return uglyNums.get(uglyNums.size() - 1); } }
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 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]