Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

264. Ugly Number II

Time: $O(n)$

Space: $O(n)$

			


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();
  }
};




			


class Solution {
  public int nthUglyNumber(int n) {
    List<Integer> 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);
  }
}




			


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]