Skip to content

Ugly Number II⚓︎

Link

Description⚓︎

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the n-th ugly number.

Example 1:

  • Input: n = 10
  • Output: 12
  • Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.

Example 2:

  • Input: n = 1
  • Output: 1
  • Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

Constraints:

  • 1 <= n <= 1690

Solution⚓︎

Way 1⚓︎

See reference (Chinese).

 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
26
27
28
29
class Solution {
public:
    int nthUglyNumber(int n) {
        array<int, 3> nums{2, 3, 5};
        unordered_set<long> seen;
        priority_queue<long, vector<long>, greater<long>> heap;
        seen.insert(1);
        heap.push(1);

        for (int i = 1; i <= n; i++) {
            long current = heap.top();
            heap.pop();

            if (i == n) {
                return static_cast<int>(current);
            }

            for (int val = 0; val < nums.size(); val++) {
                long t = nums[val] * current;
                if (!seen.count(t)) {
                    seen.insert(t);
                    heap.push(t);
                }
            }
        }

        return -1;
    }
};
  • Time complexity: \(O(n\log n)\);
  • Space complexity: \(O(n)\).

Way 2⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n + 1);
        dp[1] = 1;

        int times2 = 1, times3 = 1, times5 = 1;
        for (int index = 2; index <= n; index++) {
            int a = dp[times2] * 2, b = dp[times3] * 3, c = dp[times5] * 5;
            int current = min({a, b, c});
            if (current == a) times2++;
            if (current == b) times3++;
            if (current == c) times5++;
            dp[index] = current;
        }

        return dp[n];
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(n)\).