Summary of Ugly Numbers in Leetcode

Posted on Edited on In Waline:

Recently, leetcode’s Daily Question started a series of ugly numbers, and made a few to summarize.

Ugly number I

Link to the topic: https://leetcode-cn.com/problems/ugly-number/

There is nothing to say about this topic. Everyone should know how to do it by looking at the topic.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number} n
 * @return {boolean}
 */
var isUgly = function(n) {
    if (n <= 0) {
        return false;
    }
    const factors = [2, 3, 5];
    for (const factor of factors) {
        while (n % factor = 0) {
            n /= factor;
        }
    }
    return n  1;
};

Ugly number II

Title link

https://leetcode-cn.com/problems/ugly-number-ii/

This topic is interesting.

Minimum heap

To get the nth ugliest number from smallest to largest, you can use the minimum heap implementation.

Initially, the heap is empty. First, add the smallest ugly number, 1, to the heap.

Each time the top element x is taken out, x is the smallest ugly number in the heap. Since 2x, 3x, and 5x are also ugly numbers, 2x, 3x, and 5x are added to the heap.

The above approach will lead to duplicate elements in the heap. To avoid duplicate elements, you can use the hash set deduplicate to avoid adding the same element to the heap multiple times.

In the case of excluding duplicate elements, the nth element taken from the smallest heap is the nth ugly number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var nthUglyNumber = function(n) {
    const factors = [2, 3, 5];
    const seen = new Set();
    const heap = new MinHeap();
    seen.add(1);
    heap.insert(1);
    let ugly = 0;
    for (let i = 0; i < n; i++) {
        ugly = heap.pop();
        for (const factor of factors) {
            const next = ugly * factor;
            if (!seen.has(next)) {
                seen.add(next);
                heap.insert(next);
            }
        }
        
    }
    return ugly;
};

The implementation of the minimum heap can be seen in my other blog: https://sunra.top/posts/9df73d67/

Dynamic Programming

Method 1 Using the minimum heap will store more ugly numbers in advance, resulting in higher space complexity, and the process of maintaining the minimum heap also leads to higher time complexity. Dynamic Programming can be used for optimization.

Define an array dp, where dp [i] represents the i-th ugly number, and the nth ugly number is dp [n].

Since the smallest ugly number is 1, dp [1] = 1.

How to get the rest of the ugly numbers? Define three pointers p2, p3, p5, indicating that the next ugly number is the ugly number pointed to by the current pointer multiplied by the corresponding prime factor. Initially, the values of all three pointers are 1.

When 2 ≤ i ≤ n, let dp [i] = min (dp [p2] × 2, dp [p3] × 3, dp [p5] × 5), and then compare dp [p2], dp [p3], dp [p5] are equal, if equal, add 1 to the corresponding pointer.

This sentence may be a bit abstract

In other words, the value of px means that the number in front of px multiplied by x is already in the dp list.

For example,

p2

p3

p5

In this case, I’m going to ask for dp [i], and I’m going to start from dp [p2]

Why not go to dp [p2

Why not go to dp [p2

Why not go to dp [p3]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var nthUglyNumber = function(n) {
    const dp = new Array(n + 1).fill(0);
    dp[1] = 1;
    let p2 = 1, p3 = 1, p5 = 1;
    for (let i = 2; i <= n; i++) {
        const num2 = dp [p2] * 2, num3 = dp [p3] * 3, num5 = dp [p5] * 5;
        dp[i] = Math.min(Math.min(num2, num3), num5);
        if (dp[i] = num2) {
            p2++;
        }
        if (dp[i] = num3) {
            p3++;
        }
        if (dp[i] = num5) {
            p5++;
        }
    }
    return dp[n];
};

Reference link:

https://leetcode-cn.com/problems/ugly-number-ii/solution/chou-shu-ii-by-leetcode-solution-uoqd/