跳至主要內容

一文秒杀所有丑数系列问题

labuladong原创双指针数学约 7875 字

1201. 丑数 III https://leetcode.cn/problems/ugly-number-iii

1201. Ugly Number III https://leetcode.com/problems/ugly-number-iii

263. 丑数 https://leetcode.cn/problems/ugly-number

263. Ugly Number https://leetcode.com/problems/ugly-number

264. 丑数 II https://leetcode.cn/problems/ugly-number-ii

264. Ugly Number II https://leetcode.com/problems/ugly-number-ii

313. 超级丑数 https://leetcode.cn/problems/super-ugly-number

313. Super Ugly Number https://leetcode.com/problems/super-ugly-number

剑指 Offer 49. 丑数 https://leetcode.cn/problems/chou-shu-lcof

剑指 Offer 49. 丑数 LCOF https://leetcode.com/problems/chou-shu-lcof

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCodeDifficulty
1201. Ugly Number III🟠
263. Ugly Number🟢
264. Ugly Number II🟠
313. Super Ugly Number🟠

Prerequisites

Before reading this article, you should learn:

Recently, a reader in our group messaged me, saying they encountered a series of math-related algorithm questions during a Microsoft interview and felt overwhelmed. Upon reviewing the questions, I realized they were modified versions of the "Ugly Number" series problems on LeetCode.

Firstly, the "Ugly Number" series falls into the category of "easy for those who know, hard for those who don't," as it involves some mathematical theorems. If you haven't studied these specifically, it's unlikely you'll figure them out on your own.

Moreover, these problems heavily test abstract thinking and associative skills. Not only do they require mathematical theorems, but you also need to abstract the problem into linked list-related questions using two-pointer techniques, or into array-related questions using binary search techniques.

Today, I'll cover all "Ugly Number" related problems in one article, exploring how these problems can vary and how to solve them.

Ugly Number I

First up is LeetCode problem 263, "Ugly Number." The problem asks you to determine if a given number n is an "ugly number." An "ugly number" is a positive integer that only contains the prime factors 2, 3, and 5.

The function signature is as follows:

boolean isUgly(int n)

For example, 12 = 2 x 2 x 3 is an ugly number, while 42 = 2 x 3 x 7 is not an ugly number.

This problem is actually very simple, provided you know the Fundamental Theorem of Arithmetic (Unique Prime Factorization Theorem):

Any natural number greater than 1 is either a prime number itself or can be factored into a product of prime numbers.

Since any positive integer greater than one can be factored into a product of prime numbers, an ugly number can also be factored into a product of prime numbers, and these prime numbers can only be 2, 3, or 5.

With this understanding, you can implement the isUgly function:

java 🟢
class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) return false;
        // if n is an ugly number, its factors should only be 2, 3, 5
        while (n % 2 == 0) n /= 2;
        while (n % 3 == 0) n /= 3;
        while (n % 5 == 0) n /= 5;
        // if it can be successfully factored, it is an ugly number
        return n == 1;
    }
}

Ugly Number II

Let's increase the difficulty. Look at LeetCode problem #264 "Ugly Number II". Now, the task is not to determine if a number is an ugly number, but given an input n, you need to find the n-th ugly number. The function signature is as follows:

java 🟢
int nthUglyNumber(int n)

For example, if the input is n = 10, the function should return 12. This is because the sequence of ugly numbers from smallest to largest is 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, and the 10th ugly number is 12 (note that we count 1 as an ugly number).

This problem is quite clever. It may seem like a math problem, but it actually involves merging multiple sorted linked lists and uses the idea of sieving prime numbers.

First, in a previous article How to Efficiently Find Prime Numbers, I discussed the "sieve method" for efficiently finding prime numbers: a prime number multiplied by any number other than 1 is not a prime number. By sieving out these numbers, the remaining ones are prime.

This image from Wikipedia illustrates it well:

Based on the sieve method for prime numbers and the definition of ugly numbers, we can easily deduce a pattern: if a number x is an ugly number, then x * 2, x * 3, x * 5 are also definitely ugly numbers.

If we imagine all ugly numbers as a sorted linked list from smallest to largest, it would look like this:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 8 -> ...

Then, we can categorize ugly numbers into three types: multiples of 2, multiples of 3, and multiples of 5. These three types of ugly numbers are like three sorted linked lists, as follows:

Ugly numbers divisible by 2:

1*2 -> 2*2 -> 3*2 -> 4*2 -> 5*2 -> 6*2 -> 8*2 ->...

Ugly numbers divisible by 3:

1*3 -> 2*3 -> 3*3 -> 4*3 -> 5*3 -> 6*3 -> 8*3 ->...

Ugly numbers divisible by 5:

1*5 -> 2*5 -> 3*5 -> 4*5 -> 5*5 -> 6*5 -> 8*5 ->...

If we merge these three "sorted linked lists" together and remove duplicates, we get the sequence of ugly numbers. The n-th element in this sequence is the answer we want:

1 -> 1*2 -> 1*3 -> 2*2 -> 1*5 -> 3*2 -> 4*2 ->...

So, this is similar to the approach discussed in Summary of Two-Pointer Techniques for Linked Lists for merging two sorted linked lists. Let's first look at the core solution code for merging sorted linked lists:

java 🟢
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // Virtual head node to store the result list, pointer p points to the result list
    ListNode dummy = new ListNode(-1), p = dummy;
    
    // p1, p2 are on two sorted lists respectively
    ListNode p1 = l1, p2 = l2;
    
    while (p1 != null && p2 != null) {
        // Compare the two pointers p1 and p2
        // Connect the node with the smaller value to the result list
        if (p1.val > p2.val) {
            p.next = p2;
            p2 = p2.next;
        } else {
            p.next = p1;
            p1 = p1.next;
        }
        // Pointer p keeps moving forward
        p = p.next;
    }
    // Some non-core code is omitted...
}

For this problem, we abstract out three ordered lists of ugly numbers. Merging these three ordered lists gives us the sequence of ugly numbers, where the n-th ugly number is the answer the problem seeks.

Similar to merging two ordered lists, here is the solution code for this problem:

java 🟢
class Solution {
    public int nthUglyNumber(int n) {
        // can be understood as three pointers pointing to the head of the ordered list
        int p2 = 1, p3 = 1, p5 = 1;
        // can be understood as the value of the head node of the three ordered lists
        int product2 = 1, product3 = 1, product5 = 1;
        // can be understood as the final merged ordered list (result list)
        int[] ugly = new int[n + 1];
        // can be understood as the pointer on the result list
        int p = 1;

        // start merging the three ordered lists, and end when the nth ugly number is found
        while (p <= n) {
            // take the smallest node from the three lists
            int min = Math.min(Math.min(product2, product3), product5);
            // connect the smallest node to the result list
            ugly[p] = min;
            p++;
            // move the pointer forward on the corresponding ordered list
            if (min == product2) {
                product2 = 2 * ugly[p2];
                p2++;
            }
            if (min == product3) {
                product3 = 3 * ugly[p3];
                p3++;
            }
            if (min == product5) {
                product5 = 5 * ugly[p5];
                p5++;
            }
        }
        // return the nth ugly number
        return ugly[n];
    }
}

We use p2, p3, p5 to represent pointers on three ugly number lists, product2, product3, product5 to represent the values of nodes on the ugly number lists, and the ugly array to record the results after merging the ordered lists.

With the previous铺垫 and analogies, you should find it easy to understand the approach to this problem. Let's now increase the difficulty a bit.

Super Ugly Number

Take a look at LeetCode problem 313, "Super Ugly Number." This problem gives you a list of prime numbers primes and a positive integer n, and asks you to calculate the n-th "super ugly number." A super ugly number is a positive integer whose prime factors are all in the primes list. The function signature is as follows:

java 🟢
int nthSuperUglyNumber(int n, int[] primes)

If primes = [2, 3, 5], it refers to the previous problem, so this problem is an advanced version of the last one.

However, the approach is still similar. You still treat each prime factor as a sorted linked list. The previous problem was equivalent to merging three sorted linked lists, while this problem is like merging len(primes) sorted linked lists. This is the same idea as the "Merge K Sorted Lists" discussed in Double Pointer Techniques to Solve Seven Linked List Problems.

Note that in the previous problem, we abstracted three linked lists and needed p2, p3, p5 as pointers on these sorted linked lists. We also needed product2, product3, product5 to record the values of the nodes pointed to by these pointers. In each loop, we used the min function to calculate the smallest head node.

In this problem, it's like we have len(primes) sorted linked lists as input. We can't use the min function to find the smallest head node anymore. Instead, we need to use a priority queue to calculate the smallest head node. We still need to maintain the linked list pointers and the values of the nodes they point to. We can use a triplet to store this information.

By combining the idea of merging K sorted linked lists from Double Pointer Techniques to Solve Seven Linked List Problems, you can understand the solution to this problem:

java 🟢
class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        // the priority queue contains triples long[] {product, prime, pi}
        // where product represents the value of the list node, prime is the prime factor needed to calculate the next node, and pi is the pointer on the list
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> {
            // the priority queue is sorted by the value of the node
            return (int)(a[0] - b[0]);
        });

        // add the head nodes of multiple lists to the priority queue
        for (int i = 0; i < primes.length; i++) {
            pq.offer(new long[]{ 1, primes[i], 1 });
        }

        // can be understood as the finally merged ordered list (result list)
        long[] ugly = new long[n + 1];
        // can be understood as the pointer on the result list
        int p = 1;

        while (p <= n) {
            // take the smallest node of the three lists
            long[] pair = pq.poll();
            long product = pair[0];
            long prime = pair[1];
            int index = (int)pair[2];

            // avoid duplicate elements in the result list
            if (product != ugly[p - 1]) {
                // connect to the result list
                ugly[p] = product;
                p++;
            }

            // generate the next node and add it to the priority queue
            long[] nextPair = new long[]{ugly[index] * prime, prime, index + 1};
            pq.offer(nextPair);
        }
        return (int)ugly[n];
    }
}

Preventing int Overflow

For strongly typed languages like Java/C++/Go, be cautious of int type overflow.

Although the problem states that the n-th super ugly number will not exceed the int upper limit 2^31 - 1, overflow can still occur when calculating ugly[index] * prime. Therefore, use long or int64 types to store the triplets.

Next, let's look at the fourth ugly number problem, which is the highlight of today.

Ugly Number III

This is LeetCode problem #1201 "Ugly Number III". Here's the problem statement:

You are given four integers: n, a, b, c. Design an algorithm to find the n-th ugly number. An ugly number is a positive integer that is divisible by a, b, or c.

The difference between this problem and previous ones is that it changes the definition of an "ugly number". As long as a positive integer x has any of a, b, c as a factor, x is considered an ugly number.

For example, if the input is n = 7, a = 3, b = 4, c = 5, the algorithm should output 10. The sequence of ugly numbers meeting the criteria is 3, 4, 5, 6, 8, 9, 10, ..., and the 7th number in this sequence is 10.

With the foundation from the previous problems, you can surely think of abstracting the multiples of a, b, c into three ordered linked lists:

1*3 -> 2*3 -> 3*3 -> 4*3 -> 5*3 -> 6*3 -> 7*3 ->...
1*4 -> 2*4 -> 3*4 -> 4*4 -> 5*4 -> 6*4 -> 7*4 ->...
1*5 -> 2*5 -> 3*5 -> 4*5 -> 5*5 -> 6*5 -> 7*5 ->...

Next, merge these three linked lists into a single sorted linked list and remove duplicate elements. The resulting linked list will be the sequence of ugly numbers. From this sequence, we can find the n-th element:

1*3 -> 1*4 -> 1*5 -> 2*3 -> 2*4 -> 3*3 -> 2*5 ->...

With this approach, you can directly write the code:

java 🟢
class Solution {
    public int nthUglyNumber(int n, int a, int b, int c) {
        // can be understood as the value of the head node of three ordered linked lists
        // since the data size is large, use long type
        long productA = a, productB = b, productC = c;
        // can be understood as the pointer on the merged ordered linked list
        int p = 1;

        long min = -666;

        // start merging the three ordered linked lists to get the value of the nth node
        while (p <= n) {
            // take the smallest node of the three linked lists
            min = Math.min(Math.min(productA, productB), productC);
            p++;
            // move the pointer of the linked list corresponding to the smallest node
            if (min == productA) {
                productA += a;
            }
            if (min == productB) {
                productB += b;
            }
            if (min == productC) {
                productC += c;
            }
        }
        return (int) min;
    }
}

This approach should be very simple, but it doesn't pass all test cases after submission; it times out.

Note that the data range given in the problem is very large, with a, b, c, n potentially reaching 10^9. Therefore, even though the time complexity of the above algorithm is O(n), it is relatively time-consuming, and there should be a better approach to further reduce the time complexity.

The correct solution to this problem is quite challenging. The difficulty lies in combining some mathematical knowledge with binary search techniques to efficiently solve the problem.

First, we can define a monotonically increasing function f:

f(num, a, b, c) calculates the number of integers in the range [1..num] that are divisible by a, b, or c. Obviously, the return value of function f increases as num increases (monotonically increasing).

The problem asks us to find the n-th number that is divisible by a, b, or c. In other words, we need to find the smallest num such that f(num, a, b, c) == n.

This num is the n-th number that is divisible by a, b, or c.

Based on the approach template provided in Practical Applications of Binary Search, we have a monotonically increasing function f. To find the minimum value of the parameter num, we can apply the binary search algorithm for finding the left boundary:

java 🟢
int nthUglyNumber(int n, int a, int b, int c) {
    // the problem states that the result is within the range [1, 2 * 10^9],
    // so we initialize the search range with both ends closed according to this range
    int left = 1, right = (int) 2e9;
    // binary search for the left boundary
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (f(mid, a, b, c) < n) {
            // there are not enough elements meeting the criteria in [1..mid], so the target is on the right half
            left = mid + 1;
        } else {
            // the number of elements meeting the criteria in [1..mid] is greater than n, so the target is on the left half
            right = mid - 1;
        }
    }
    return left;
}

// function f is a monotonic function
// calculate how many numbers in [1..num] can be divided by a, b, or c
long f(int num, int a, int b, int c) {
    // implementation below
}

// ... other code

The binary search code template for finding the left boundary was discussed in Binary Search Framework Explanation. There's not much to add there. The key point is how to implement the function f, which involves set theory theorems and methods for calculating the least common multiple (LCM) and greatest common divisor (GCD).

First, let's define the set A as the numbers in [1..num] that are divisible by a, set B as those divisible by b, and set C as those divisible by c. Therefore, len(A) = num / a, len(B) = num / b, and len(C) = num / c, which is straightforward.

However, the value of f(num, a, b, c) is not simply num / a + num / b + num / c. This is because some numbers may be divisible by two or all three of a, b, and c, as shown in the diagram below:

According to set theory, the elements in this set should be: A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C. This should be clear with the help of the diagram.

The question arises, how do we calculate the number of elements in intersections like A ∩ B?

It's actually quite simple. The number of elements in A ∩ B is num / lcm(a, b), where lcm is the function to calculate the least common multiple.

Similarly, the number of elements in A ∩ B ∩ C is num / lcm(lcm(a, b), c).

Now, how do we find the least common multiple?

Just remember this theorem: lcm(a, b) = a * b / gcd(a, b), where gcd is the function to calculate the greatest common divisor.

Next, how do we find the greatest common divisor? This is a classic algorithm, commonly known as the Euclidean algorithm (or辗转相除算法 in Chinese).

With all these nested concepts, we can finally translate this logic into code to implement the f function. Note that due to the large data size in this problem, sometimes we need to use the long type to prevent int overflow:

java 🟢
class Solution {
    public int nthUglyNumber(int n, int a, int b, int c) {
        // the problem states that the result is within the range [1, 2 * 10^9],
        // so initialize the search range with both ends closed according to this range
        int left = 1, right = (int) 2e9;
        // binary search for the left boundary
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (f(mid, a, b, c) < n) {
                // the number of elements that meet the condition in [1..mid] is less than n, so the target is on the right half
                left = mid + 1;
            } else {
                // the number of elements that meet the condition in [1..mid] is greater than n, so the target is on the left half
                right = mid - 1;
            }
        }
        return left;
    }

    // calculate the greatest common divisor (Euclidean algorithm)
    long gcd(long a, long b) {
        if (a < b) {
            // ensure a > b
            return gcd(b, a);
        }
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    // least common multiple
    long lcm(long a, long b) {
        // the least common multiple is the product divided by the greatest common divisor
        return a * b / gcd(a, b);
    }

    // calculate how many numbers between [1..num] can be divided by a or b or c
    long f(int num, int a, int b, int c) {
        long setA = num / a, setB = num / b, setC = num / c;
        long setAB = num / lcm(a, b);
        long setAC = num / lcm(a, c);
        long setBC = num / lcm(b, c);
        long setABC = num / lcm(lcm(a, b), c);
        // set theory theorem: A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C
        return setA + setB + setC - setAB - setAC - setBC + setABC;
    }
}

By implementing the f function and combining it with the previous binary search template, the time complexity is reduced to logarithmic level, allowing for an efficient solution to this problem.

This concludes all the problems related to "ugly numbers," which involve knowledge points such as the fundamental theorem of arithmetic, merging multiple sorted linked lists, binary search templates, the Euclidean algorithm, and more. If you haven't encountered similar problems before, it might be challenging to come up with solutions. However, once you've practiced them, solving these problems becomes straightforward. Therefore, I consider these mathematical problems to be of the type that are easy for those who know and hard for those who don't.

For more mathematical algorithms, see How to Efficiently Find Prime Numbers, Discussing Random Algorithms in Games, Common Bit Manipulations, and Algorithm Problems Solvable with a Single Line of Code.

引用本文的题目

安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：

LeetCode力扣
-剑指 Offer 49. 丑数
上次编辑于: